1
vote
1answer
43 views

Boolean algebra generated by value sets of polynomials over $\mathbb{N}$

Update For each polynomial $P \in \mathbb{N}[X]$, let $S_P = \{ P(n) \mid n \in \mathbb{N}\}$. Does the Boolean algebra generated by the subsets $S_P$ of $\mathcal{P}(\mathbb{N})$ such that $P$ is ...
1
vote
0answers
39 views

Given a finite set of points construct a polynomial that meets the points.

Say I have a set of points in $\mathbb{Z}^3 \times \mathbb{Z}_2$ each of which represent part of a mapping $(z_1, z_2, z_3) \mapsto z_4 \in \mathbb{Z}_2$. How do I find the the simplest polynomial ...
3
votes
1answer
40 views

The set of all polynomial functions from $\mathbb{Z}^3 \rightarrow \mathbb{Z}/(2)$

Let $f:\mathbb{Z}^3 \rightarrow \mathbb{Z}_2$ be a polynomial function in $\mathbb{Z}[x_1, x_2, x_3]$. Then $f$ has the form $f(x_1, x_2, x_3) = c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 ...
1
vote
2answers
86 views

Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...
2
votes
1answer
110 views

Extending the logical-or function to a low degree polynomial over a finite field

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Is there ...
3
votes
3answers
157 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...