How to evaluate all the essentially distinct polynomials in 4 variables over $F_2$ on points of $F_2 ^ 4$

Question

I am a beginner with Mathematica. For my research purpose I would like to get a list of all the polynomials in $F_2[x,y,z,w]$ and for each polynomial I would like to know the result that it gives then it is applied on each point on $F_2 ^ 4$. More concretely, F_2={0,1}.Take 2 variables x and y. Consider all possible polynomials, where degree of both x and y are less than or equal to 1.you have usual multiplication and addition modulo 2.(that means whatever you get by adding or multiplying elements of F_2 take the remainder when divided by 2). The desired answer would be like,

Polynomials (0,0) (0, 1) (1,0) (1,1)

 x         0     0     1     1 

likewise consider all other polynomials with the property given above and I would like to get a table of what values the polynomial takes at the given point, like I have mentioned for the polynomial x.

Any help will be appreciated.

Answer 1

[This is a revision of the original inefficient and largely buggy method I first posted.]

Here is a way to get all the linear polynomials in GF(2)(variables).

polys[vars_] := Module[
  {mmonoms, len = Length[vars]},
  monoms = 
   Prepend[Table[
     Apply[Times, vars.IntegerDigits[j, 2, len]], {j, 1, 2^len - 1}], 
    1];
  len = Length[monoms];
  Table[Total[Pick[monoms, IntegerDigits[j, 2, len], 1]], {j, 0, 
    2^len - 1}]]

(* {0, 1, x, 1 + x, y, x y, 1 + y, x + y, 1 + x + y, 1 + x y, x + x y, 
 1 + x + x y, y + x y, 1 + y + x y, x + y + x y, 1 + x + y + x y, z, 
 x z, y z, x y z, 1 + z, x + z, 1 + x + z, y + z, 1 + y + z, 
 x + y + z, 1 + x + y + z, x y + z, 1 + x y + z, x + x y + z, 
 1 + x + x y + z, y + x y + z, 1 + y + x y + z, x + y + x y + z, 
 1 + x + y + x y + z, 1 + x z, x + x z, 1 + x + x z, y + x z, 
 1 + y + x z, x + y + x z, 1 + x + y + x z, x y + x z, 1 + x y + x z, 
 x + x y + x z, 1 + x + x y + x z, y + x y + x z, 1 + y + x y + x z, 
 x + y + x y + x z, 1 + x + y + x y + x z, z + x z, 1 + z + x z, 
 x + z + x z, 1 + x + z + x z, y + z + x z, 1 + y + z + x z, 
 x + y + z + x z, 1 + x + y + z + x z, x y + z + x z, 
 1 + x y + z + x z, x + x y + z + x z, 1 + x + x y + z + x z, 
 y + x y + z + x z, 1 + y + x y + z + x z, x + y + x y + z + x z, 
 1 + x + y + x y + z + x z, 1 + y z, x + y z, 1 + x + y z, y + y z, 
 1 + y + y z, x + y + y z, 1 + x + y + y z, x y + y z, 1 + x y + y z, 
 x + x y + y z, 1 + x + x y + y z, y + x y + y z, 1 + y + x y + y z, 
 x + y + x y + y z, 1 + x + y + x y + y z, z + y z, 1 + z + y z, 
 x + z + y z, 1 + x + z + y z, y + z + y z, 1 + y + z + y z, 
 x + y + z + y z, 1 + x + y + z + y z, x y + z + y z, 
 1 + x y + z + y z, x + x y + z + y z, 1 + x + x y + z + y z, 
 y + x y + z + y z, 1 + y + x y + z + y z, x + y + x y + z + y z, 
 1 + x + y + x y + z + y z, x z + y z, 1 + x z + y z, x + x z + y z, 
 1 + x + x z + y z, y + x z + y z, 1 + y + x z + y z, 
 x + y + x z + y z, 1 + x + y + x z + y z, x y + x z + y z, 
 1 + x y + x z + y z, x + x y + x z + y z, 1 + x + x y + x z + y z, 
 y + x y + x z + y z, 1 + y + x y + x z + y z, 
 x + y + x y + x z + y z, 1 + x + y + x y + x z + y z, z + x z + y z, 
 1 + z + x z + y z, x + z + x z + y z, 1 + x + z + x z + y z, 
 y + z + x z + y z, 1 + y + z + x z + y z, x + y + z + x z + y z, 
 1 + x + y + z + x z + y z, x y + z + x z + y z, 
 1 + x y + z + x z + y z, x + x y + z + x z + y z, 
 1 + x + x y + z + x z + y z, y + x y + z + x z + y z, 
 1 + y + x y + z + x z + y z, x + y + x y + z + x z + y z, 
 1 + x + y + x y + z + x z + y z, 1 + x y z, x + x y z, 1 + x + x y z,
  y + x y z, 1 + y + x y z, x + y + x y z, 1 + x + y + x y z, 
 x y + x y z, 1 + x y + x y z, x + x y + x y z, 1 + x + x y + x y z, 
 y + x y + x y z, 1 + y + x y + x y z, x + y + x y + x y z, 
 1 + x + y + x y + x y z, z + x y z, 1 + z + x y z, x + z + x y z, 
 1 + x + z + x y z, y + z + x y z, 1 + y + z + x y z, 
 x + y + z + x y z, 1 + x + y + z + x y z, x y + z + x y z, 
 1 + x y + z + x y z, x + x y + z + x y z, 1 + x + x y + z + x y z, 
 y + x y + z + x y z, 1 + y + x y + z + x y z, 
 x + y + x y + z + x y z, 1 + x + y + x y + z + x y z, x z + x y z, 
 1 + x z + x y z, x + x z + x y z, 1 + x + x z + x y z, 
 y + x z + x y z, 1 + y + x z + x y z, x + y + x z + x y z, 
 1 + x + y + x z + x y z, x y + x z + x y z, 1 + x y + x z + x y z, 
 x + x y + x z + x y z, 1 + x + x y + x z + x y z, 
 y + x y + x z + x y z, 1 + y + x y + x z + x y z, 
 x + y + x y + x z + x y z, 1 + x + y + x y + x z + x y z, 
 z + x z + x y z, 1 + z + x z + x y z, x + z + x z + x y z, 
 1 + x + z + x z + x y z, y + z + x z + x y z, 
 1 + y + z + x z + x y z, x + y + z + x z + x y z, 
 1 + x + y + z + x z + x y z, x y + z + x z + x y z, 
 1 + x y + z + x z + x y z, x + x y + z + x z + x y z, 
 1 + x + x y + z + x z + x y z, y + x y + z + x z + x y z, 
 1 + y + x y + z + x z + x y z, x + y + x y + z + x z + x y z, 
 1 + x + y + x y + z + x z + x y z, y z + x y z, 1 + y z + x y z, 
 x + y z + x y z, 1 + x + y z + x y z, y + y z + x y z, 
 1 + y + y z + x y z, x + y + y z + x y z, 1 + x + y + y z + x y z, 
 x y + y z + x y z, 1 + x y + y z + x y z, x + x y + y z + x y z, 
 1 + x + x y + y z + x y z, y + x y + y z + x y z, 
 1 + y + x y + y z + x y z, x + y + x y + y z + x y z, 
 1 + x + y + x y + y z + x y z, z + y z + x y z, 1 + z + y z + x y z, 
 x + z + y z + x y z, 1 + x + z + y z + x y z, y + z + y z + x y z, 
 1 + y + z + y z + x y z, x + y + z + y z + x y z, 
 1 + x + y + z + y z + x y z, x y + z + y z + x y z, 
 1 + x y + z + y z + x y z, x + x y + z + y z + x y z, 
 1 + x + x y + z + y z + x y z, y + x y + z + y z + x y z, 
 1 + y + x y + z + y z + x y z, x + y + x y + z + y z + x y z, 
 1 + x + y + x y + z + y z + x y z, x z + y z + x y z, 
 1 + x z + y z + x y z, x + x z + y z + x y z, 
 1 + x + x z + y z + x y z, y + x z + y z + x y z, 
 1 + y + x z + y z + x y z, x + y + x z + y z + x y z, 
 1 + x + y + x z + y z + x y z, x y + x z + y z + x y z, 
 1 + x y + x z + y z + x y z, x + x y + x z + y z + x y z, 
 1 + x + x y + x z + y z + x y z, y + x y + x z + y z + x y z, 
 1 + y + x y + x z + y z + x y z, x + y + x y + x z + y z + x y z, 
 1 + x + y + x y + x z + y z + x y z, z + x z + y z + x y z, 
 1 + z + x z + y z + x y z, x + z + x z + y z + x y z, 
 1 + x + z + x z + y z + x y z, y + z + x z + y z + x y z, 
 1 + y + z + x z + y z + x y z, x + y + z + x z + y z + x y z, 
 1 + x + y + z + x z + y z + x y z, x y + z + x z + y z + x y z, 
 1 + x y + z + x z + y z + x y z, x + x y + z + x z + y z + x y z, 
 1 + x + x y + z + x z + y z + x y z, y + x y + z + x z + y z + x y z,
  1 + y + x y + z + x z + y z + x y z, 
 x + y + x y + z + x z + y z + x y z, 
 1 + x + y + x y + z + x z + y z + x y z} *)

To get higher degrees one might use the Outer approach to get products of pairs, triples, etc.

As for evaluations, Could do e.g. PolynomialMod[pol /. {x->1,y->0,z->1},2] and it's not hard to cycle through all possible 0-1 combinations for the variables (same idea as what I did to produce the polynomials from monomial lists).

Answer 2

The distinction between a polynomial and a polynomial function is important. For example, over $\mathbb{F}_2$, the polynomials $x^2$ and $x$ are distinct but they determine the same function (as you can check by plugging $0$ and $1$ into both).

Do you perhaps want to enumerate polynomial functions? If so, then--by using Lagrange Interpolation, for instance--it is easy to show that all functions on a finite field $\mathbb{F}$ with $q$ elements are polynomial functions. If you're unfamiliar with this method, let $x_1, \ldots, x_n$ be $n\ge 1$ variables and let $f: \mathbb{F}^n\to \mathbb{F}$ be any function at all. For any vector $a = (a_1, \ldots, a_n)$ in $\mathbb{F}^n$, define the function

$$e_{a}: a \to 1,\quad a'\to 0 \text{ if }a' \ne a.$$

We can construct a polynomial representation of this function. For any element $u\in \mathbb{F}$, the monomial of degree $q-1$ in $x$,

$$m_{u}(x) = \frac{\prod_{v\ne u}(x-v)}{\prod_{v\ne u}(u-v)},$$

is well-defined because every element in the denominator product, being nonzero, is invertible ($\mathbb{F}$ is a field). This monomial clearly vanishes everywhere on $\mathbb{F}$ except at $x=u$, where the equality of numerator and denominator show it equals $1$. It is immediate that the product

$$p_a(x) = m_{a_1}(x_1)m_{a_2}(x_2)\cdots m_{a_n}(x_n),$$

considered as a polynomial function, equals $e_{a}$. Whence

$$f(u_1, \cdots, u_n) = \sum_{a\in \mathbb{F}^n} f(a)p_a(u)$$

is a polynomial function and the maximum degree in each variable does not exceed $q-1$ (which is $1$ when $q=2$, as in the question).

With $n$ variables and a field of $q$ elements there are $q^n$ elements in $\mathbb{F}^n$ and therefore $q^{q^n}$ such polynomial functions: that's your answer. I don't see any point to listing them all, because this is every possible function that can be defined on $\mathbb{F}^n$ (as a set) into $\mathbb{F}$.

---

Edit

Applying these ideas to the case $q=2$ we obtain this efficient solution to enumerating all polynomials of maximum degree $1$:

With[{n = 4}, 
  Plus @@@ Subsets[Array[Symbol["x" <> ToString[#]] &, n] . # 
    /. {Plus -> Times, 0 -> 1} & /@ Tuples[{0, 1}, n]]]

(0.15 seconds, 65536 elements).

Working from inside out, this expression:

• Generates $n$ variable symbols $x1, \ldots, xn$ (Symbol).

• Generates all possible lists of powers of these variables. Because the powers are in $\{0,1\}$, these lists correspond to all $n$-tuples of $\{0,1\}$ (Tuples).

• Converts each tuple into a monomial (via Dot followed by converting addition to multiplication).

• Because the field has only two elements, whence the coefficients can only be $0$ or $1$, every possible polynomial is determined uniquely by a subset of this collection of monomials (Subsets, with List replaced by Plus via @@@).

As an example, with n=2 (and using Subscript instead of Symbol for nice formatting), the output is

$\{0,1,x_2,x_1,x_1 x_2,1+x_2,1+x_1,1+x_1 x_2,x_1+x_2,x_2+x_1 x_2,x_1+x_1 x_2,\\1+x_1+x_2,1+x_2+x_1 x_2,1+x_1+x_1 x_2,x_1+x_2+x_1 x_2,1+x_1+x_2+x_1 x_2\}$

Answer 3

Edit: I just discovered another way to get all monomials:

Subsets[x y z]
(* {1, x, y, z, x y, x z, y z, x y z} *)

---

Do you count 1+x and 1+x^2 as essentially distinct polynomials or the same function?

If distinct (they have different splitting fields), then there are infinitely many polynomials.

If you're comparing them as functions, then there are 2^(2^4) = 65536 of them:

Total /@ Tuples[{0, #} & /@ Subsets[x y z w]]

More succinctly, but a little slower:

gen[vars_] := Tuples[{0, 1}, 2^Length[vars]].Subsets[Times @@ vars]
gen[{w,x,y,z}]
(* output omitted *)

(In fact, they cover all functions of four variables mod 2.)