0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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, could you please provide some more information about these $F$-spaces?) $\endgroup$ Commented Mar 14, 2013 at 11:11
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 12:07
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 12:59
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 13:17
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 13:33

3 Answers 3

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, Daniel for your kind reply. Is it possible to contact you by email? $\endgroup$ Commented Mar 14, 2013 at 15:37
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 16:39
8
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 17:03
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 18:23
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 18:40
  • $\begingroup$ ya...what is gained? for example it would give an idea about the generalized hamming weight of Reed Muller Codes.... $\endgroup$ Commented Mar 14, 2013 at 18:56
  • $\begingroup$ 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. $\endgroup$ Commented Mar 14, 2013 at 18:58
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hey Michael, 1+x and 1+x^2 are not distinct, since over F_2 both will give the same value.... $\endgroup$ Commented Mar 14, 2013 at 15:41
  • $\begingroup$ @MrinmoyDatta Thanks. I saw that in a comment after I had posted. $\endgroup$ Commented Mar 14, 2013 at 15:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.