# polynomials

A mathematical expression formed from constants and nonnegative integer powers of variables; in complexity theory, polynomial bounds describe computation measures such as time or memory as a function of problem size.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Remez and function approximations

DevFeed: [Remez and function approximations](<https://devfeed.tech/articles/remez-and-function-approximations-40500.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/shortform/2024-05-06-1018/>)

Published: 2024-05-06T17:18:29Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [FHE](<https://devfeed.tech/topics/fhe.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [article](<https://devfeed.tech/tags/article.md>), [fhe](<https://devfeed.tech/tags/fhe.md>), [homomorphic-encryption](<https://devfeed.tech/tags/homomorphic-encryption.md>), [how-to](<https://devfeed.tech/tags/how-to.md>), [library](<https://devfeed.tech/tags/library.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [python](<https://devfeed.tech/tags/python.md>), [remez](<https://devfeed.tech/tags/remez.md>), [shortform](<https://devfeed.tech/tags/shortform.md>)

### AI overview

The article discusses approximating functions with low-degree polynomials for arithmetic fully homomorphic encryption. It examines lolremez, the Remez algorithm, Paterson-Stockmeyer evaluation, and a multi-interval Remez method for approximating discontinuous functions such as sign.

### Source excerpt

I've been learning recently about how to approximate functions by low-degree polynomials. This is useful in fully homomorphic encryption (FHE) in the context of "arithmetic FHE" (see my FHE overview article), where the computational model makes low-degree polynomials cheap to evaluate and non-polynomial functions expensive or impossible. In browsing the state of the art I came across two interesting things. The first is the software package lolremez that implements polynomial (and rational polynomial $f(x) / g(x)$) function approximation using the so-called Remez algorithm.

## MLIR -- Defining a New Dialect

DevFeed: [MLIR -- Defining a New Dialect](<https://devfeed.tech/articles/mlir-defining-a-new-dialect-40471.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2023/08/21/mlir-defining-a-new-dialect/>)

Published: 2023-08-21T08:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Code generation](<https://devfeed.tech/topics/code-generation.md>), [Tutorial](<https://devfeed.tech/topics/tutorial.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Compiler](<https://devfeed.tech/topics/compiler.md>)

Tags: [code](<https://devfeed.tech/tags/code.md>), [code-generation](<https://devfeed.tech/tags/code-generation.md>), [compilers](<https://devfeed.tech/tags/compilers.md>), [define](<https://devfeed.tech/tags/define.md>), [endif](<https://devfeed.tech/tags/endif.md>), [ifdef](<https://devfeed.tech/tags/ifdef.md>), [include](<https://devfeed.tech/tags/include.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [mlir](<https://devfeed.tech/tags/mlir.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [tablegen](<https://devfeed.tech/tags/tablegen.md>), [tutorial](<https://devfeed.tech/tags/tutorial.md>), [undef](<https://devfeed.tech/tags/undef.md>)

### AI overview

This tutorial explains how to define a new MLIR dialect for arithmetic on single-variable polynomials with 32-bit unsigned integer coefficients. It covers the design, an empty dialect, generated code, registration, and a simple custom type.

### Source excerpt

Table of Contents In the last article in the series, we migrated the passes we had written to use the tablegen code generation framework. That was a preface to using tablegen to define dialects. In this article we'll define a dialect that represents arithmetic on single-variable polynomials, with coefficients in $\mathbb{Z} / 2^{32} \mathbb{Z}$ (32-bit unsigned integers). The code for this article is in this pull request, and as usual the commits are organized to be read in order.

## Negacyclic Polynomial Multiplication

DevFeed: [Negacyclic Polynomial Multiplication](<https://devfeed.tech/articles/negacyclic-polynomial-multiplication-40460.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2022/12/09/negacyclic-polynomial-multiplication/>)

Published: 2022-12-09T13:35:45Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [Encryption](<https://devfeed.tech/topics/encryption.md>), [Python](<https://devfeed.tech/topics/python.md>), [GitHub](<https://devfeed.tech/topics/github.md>)

Tags: [article](<https://devfeed.tech/tags/article.md>), [complex-twist](<https://devfeed.tech/tags/complex-twist.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [github](<https://devfeed.tech/tags/github.md>), [homomorphic-encryption](<https://devfeed.tech/tags/homomorphic-encryption.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [negacyclic](<https://devfeed.tech/tags/negacyclic.md>), [polynomial-ring](<https://devfeed.tech/tags/polynomial-ring.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

### AI overview

This tutorial explains three techniques for computing negacyclic polynomial products, including the simpler cyclic product as a precursor. It places these operations in the context of lattice cryptography and fully homomorphic encryption and provides Python code on GitHub.

### Source excerpt

In this article I'll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we'll cover the simpler cyclic product. All of the Python code written for this article is on GitHub.

## Polynomial Multiplication Using the FFT

DevFeed: [Polynomial Multiplication Using the FFT](<https://devfeed.tech/articles/polynomial-multiplication-using-the-fft-40459.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/>)

Published: 2022-11-16T08:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [NumPy](<https://devfeed.tech/topics/numpy.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arrays](<https://devfeed.tech/tags/arrays.md>), [efficiently](<https://devfeed.tech/tags/efficiently.md>), [fft](<https://devfeed.tech/tags/fft.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [polynomial-interpolation](<https://devfeed.tech/tags/polynomial-interpolation.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

### AI overview

This tutorial explains how to multiply two polynomials efficiently using the Fast Fourier Transform. It contrasts the naive O(n^2) approach with polynomial interpolation, pointwise multiplication, and carefully chosen roots of unity that enable reusable computations.

### Source excerpt

Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): """Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. """ deg1 = p1.shape[0] - 1 deg2 = p1.shape[0] - 1 # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1 total_num_pts = 2 * (deg1 + deg2) next_power_of_2 = 1 << (total_num_pts - 1).

## Boolean Logic in Polynomials

DevFeed: [Boolean Logic in Polynomials](<https://devfeed.tech/articles/boolean-logic-in-polynomials-40414.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2017/07/24/boolean-logic-in-quadratic-polynomials/>)

Published: 2017-07-24T09:00:38Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>), [Optimization](<https://devfeed.tech/topics/optimization.md>)

Tags: [boolean](<https://devfeed.tech/tags/boolean.md>), [boolean-satisfiability](<https://devfeed.tech/tags/boolean-satisfiability.md>), [logic](<https://devfeed.tech/tags/logic.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>)

### AI overview

This tutorial shows how to represent Boolean logic formulas with polynomials by using multiplication for conjunction and 1 minus a variable for negation. It explains how the construction relates Boolean satisfiability to the hardness of multivariable polynomial root-finding and constrained polynomial optimization.

### Source excerpt

Problem: Express a boolean logic formula using polynomials. I.e., if an input variable $ x$ is set to $ 0$, that is interpreted as false, while $ x=1$ is interpreted as true. The output of the polynomial should be 0 or 1 according to whether the formula is true or false as a whole. Solution: You can do this using a single polynomial. Illustrating with an example: the formula is $ \neg[(a \vee b) \wedge (\neg c \vee d)]$ also known as

## Sums of k Powers

DevFeed: [Sums of k Powers](<https://devfeed.tech/articles/sums-of-k-powers-40216.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/01/sums-of-k-powers/>)

Published: 2011-07-01T12:52:29Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [context](<https://devfeed.tech/topics/context.md>)

Tags: [complex-numbers](<https://devfeed.tech/tags/complex-numbers.md>), [factoring](<https://devfeed.tech/tags/factoring.md>), [finite-fields](<https://devfeed.tech/tags/finite-fields.md>), [induction](<https://devfeed.tech/tags/induction.md>), [polynomial-ring](<https://devfeed.tech/tags/polynomial-ring.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>)

### AI overview

The article proves the geometric-series identity for sums of powers using base-k notation, polynomial factorization, and mathematical induction. It also explains extensions of the identity to fields such as the complex numbers and finite fields.

### Source excerpt

Problem: Prove that for all $ n,k \in \mathbb{N}, k > 1$, we have $$\sum \limits_{i=0}^{n} k^i = \frac{k^{n+1}-1}{k-1}$$ Solution: Representing the numbers in base $ k$, we have that each term of the sum is all 0's except for a 1 in the $ i$th place. Hence, the sum of all terms is the $ n$-digit number comprised of all 1's. Multiplying by $ k-1$ gives us the $ n$-digit number where every digit is $ k-1$.