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

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.

-
Welcome to Mathematica.SE! Please post what you have tried so far. It is very difficult for anyone to help you starting from zero. (And for those of us who are not professional mathematicians, cou,d you please provide some more information about these $F$-spaces?) – Verbeia Mar 14 '13 at 11:11
Thank you for your reply. Actually $F_2$ means finite field with two elements. Since I am new to mathematica programming I could not proceed any far. – Mrinmoy Datta Mar 14 '13 at 12:07
I think we can answer this, but don't know enough about F2 to understand what you are asking. Can you give a simple example? Say instead of four variables, give us a 2-variable version and explain what the desired answer will look like. – bill s Mar 14 '13 at 12:59
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. – Mrinmoy Datta Mar 14 '13 at 13:17
Have you looked at the Finite Fields package? reference.wolfram.com/mathematica/FiniteFields/guide/… This has commands like GF[p,q] which shows the Galois field with p elements and degree q. – bill s Mar 14 '13 at 13:33

[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).

-
Thank you, Daniel for your kind reply. Is it possible to contact you by email? – Mrinmoy Datta Mar 14 '13 at 15:37
It is more efficient and effective to work through MSE. That way more questions can be covered, and the work is spread out better as well. – Daniel Lichtblau Mar 14 '13 at 16:39

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\}$

-
This covers the same ground as @Michael E2's brief comments in his answer. I wrote it shortly after the question appeared but suppressed it when the question was edited to limit the degrees of the polynomials, because it seemed like it might be in the process of changing into something more meaningful and interesting. In light of an accumulation of comments, though, it seemed that some elaboration of Michael's points might be useful. – whuber Mar 14 '13 at 17:03
Actually I want to list the polynomials and their values at each point which is needed for my research on Reed Muller Codes. I have already mentioned the word "essentially different" to clarify why I am limiting the degree. – Mrinmoy Datta Mar 14 '13 at 18:23
Several points: (1) it was not clear what you had meant by "essentially different"; (2) the analysis I provide here shows that nothing more would be achieved by extending the degrees when $q=2$; (3) when $q=2$, because there are $2^n$ monomials up to degree $1$ (including a constant), there is a one-to-one correspondence between the polynomials up to degree $1$ and polynomial functions. I wonder what is gained, then, by enumerating all $2^{16}$ polynomials compared to just writing a function that evaluates any polynomial. – whuber Mar 14 '13 at 18:40
ya...what is gained? for example it would give an idea about the generalized hamming weight of Reed Muller Codes.... – Mrinmoy Datta Mar 14 '13 at 18:56
Perhaps, then, your real question is not to enumerate polynomial functions, but to compute and explore the weight distributions of related codes. If that's so, you might find it more productive to ask for that instead. – whuber Mar 14 '13 at 18:58

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.)

-
Hey Michael, 1+x and 1+x^2 are not distinct, since over F_2 both will give the same value.... – Mrinmoy Datta Mar 14 '13 at 15:41
@MrinmoyDatta Thanks. I saw that in a comment after I had posted. – Michael E2 Mar 14 '13 at 15:55
I would like to know something more I need. Can you please give me some references? or can I contact you by mail? – Mrinmoy Datta Mar 14 '13 at 16:39