Message Boards Message Boards


Question concerning finite fields

Posted 9 years ago
6 Replies
2 Total Likes

I have a problem that I would like Mathematica could solve for me, but haven’t been able to do it. I thought about using the Table command, but that command would show millions of solutions (in case the computer has enough memory available) while I only want a very, very, small fraction of them.

The question is the following: I have 2 expressions (which may be called F(i,j,k) and G(i,j,k)) and I would like that Mathematica would test if F(i,j,k)=0 and G(i,j,k)=1 for all i, j and k belonging to the set {0,1,2…,728}. Then I would like to throw away those (i, j, k) such that both i, j and k are multiples of 28. Only the remaining interest me.

This is a question related to finite fields. I wish simply to know if a system of equations has solutions in the field of order 729=3^6 that are not in the smaller field of order 27=3^3.

I don’t know if Mathematica can do this. In spite of having to do 729 * 729 * 729 calculations (this would take days to compute?) the expected results should be manageable (several hundreds, at most). In case you are interested the expressions F(i,j,k) and G(i,j,k) are:

PolynomialMod[PolynomialMod[2 (w^i)^43 (w^j) + 2 (w^i)^30 (w^j)^14 + (w^i)^17 (w^j)^27 + (w^i)^4 (w^j)^40 + (w^ i)^39 (w^j)^4 (w^k) + (w^i)^13 (w^j)^30 (w^k) +  2 (w^j)^43 (w^k) + (w^i)^9 (w^j)^33 (w^k)^2 + (w^i)^31 (w^j)^10 (w^ k)^3 +2 (w^i)^5 (w^j)^36 (w^k)^3 + (w^i)^40 (w^k)^4 + (w^ i)^27 (w^j)^13 (w^k)^4 +(w^i) (w^j)^39 (w^k)^4 + 2 (w^i)^36 (w^j)^3 (w^k)^5 + 2 (w^i)^28 (w^j)^9 (w^k)^7 + (w^i)^33 (w^j)^2 (w^k)^9 +2(w^i)^7 (w^j)^28 (w^k)^9 + (w^i)^3 (w^j)^31 (w^k)^10 + (w^i)^30 (w^ j) (w^k)^13 + (w^i)^4 (w^j)^27 (w^k)^13 + 2 (w^j)^30 (w^k)^14 + (w^i)^27 (w^k)^17 + (w^i)^13 (w^j)^4 (w^ k)^27 + (w^j)^17 (w^k)^27 + 2 (w^i)^9 (w^j)^7 (w^k)^28 + 2 (w^i)^14 (w^k)^30 + (w^i) (w^j)^13 (w^k)^30 +(w^i)^10 (w^j)^3 (w^ k)^31 + (w^i)^2 (w^j)^9 (w^k)^33 + 2 (w^i)^3 (w^j)^5 (w^k)^36 + (w^i)^4 (w^j) (w^k)^39 + (w^j)^4 (w^ k)^40 + 2 (w^i) (w^k)^43, w^52-1],3]

PolynomialMod[PolynomialMod[ (w^i)^52 + (w^i)^39 (w^j)^13 + (w^i)^13 (w^j)^39 + (w^j)^52 +  2 (w^i)^48 (w^j)^3 (w^k) +  2 (w^i)^9 (w^j)^42 (w^k) + 
(w^i)^40 (w^j)^9 (w^k)^3 + 2 (w^i)^27 (w^j)^22 (w^k)^3 + 2 (w^i) (w^j)^48 (w^k)^3 + (w^i)^36 (w^j)^12 (w^k)^4 +(w^i)^28 (w^ j)^18 (w^k)^6 + 2 (w^i)^42 (w^j) (w^k)^9 +2 (w^i)^16 (w^j)^27 (w^k)^9 + (w^i)^3(w^j)^40 (w^k)^9 + (w^i)^12 (w^ j)^30 (w^k)^10 + (w^i)^30 (w^j)^10 (w^k)^12 + (w^i)^4 (w^j)^36 (w^ k)^12 + (w^i)^39 (w^k)^13 + (w^j)^39 (w^k)^13 + 2 (w^i)^27 (w^j)^9 (w^k)^16 + (w^i)^6 (w^j)^28 (w^k)^18 +  2 (w^i)^3 (w^j)^27 (w^k)^22 + 2 (w^i)^22 (w^j)^3 (w^k)^27 +  2 (w^i)^9 (w^j)^16 (w^k)^27 + (w^i)^18 (w^j)^6 (w^k)^28 + (w^ i)^10 (w^j)^12 (w^k)^30 + (w^i)^12 (w^j)^4 (w^k)^36 + (w^i)^13 (w^ k)^39 + (w^j)^13 (w^k)^39 + (w^i)^9 (w^j)^3 (w^k)^40 + 2 (w^i) (w^j)^9 (w^k)^42 +2 (w^i)^3 (w^j) (w^k)^48 + (w^k)^52, w^52-1],3]

One last question: I suppose that Mathematica orders (i, j, k) with lexicographical order. Do you know any command that asks Mathematica to compute the “first” (in the order it uses) 10.000 or 100.000 (or any other quantity) (i, j, k) and hours or days later continue from where it stopped?

POSTED BY: Joaquim Nogueira
6 Replies

Again my mistake. I forgot that in Mathematica the symbol "=" is represented by "=="

Anyway, thank you for all the help.

Joaquim Nogueira

POSTED BY: Joaquim Nogueira
POSTED BY: Joaquim Nogueira

Given that you seek solutions in certain extension fields, how is it that the two polynomials have become univariate? Maybe you are substituting powers of the polynomial variable, w, into polynomial coefficients in the defining variable(s) that give the extension(s)? It's not really clear.

POSTED BY: Daniel Lichtblau

It could be structured like this.

    {i,0.728}, {j,0,728}, {k,0,728}]]

That at least is a way to start out. There may be better ways to go about this, I'm not sure.

POSTED BY: Daniel Lichtblau

It's less than a billion cases. Should not take too long.

Also I should mention that nested PolynomialMod statements are not needed.

One other thing: if you are treating integers mod 729 as equivalent to the field of 3^6 elements, that won't work.

POSTED BY: Daniel Lichtblau

Thank you for your reply. I knw that the integers mod 729 are not the field with 729 elements. One can write that field as the splitting field of an irreducible polynomial of degree 6 in GF(3). I agree with you that the computation shouldn´t take long... but I don't know how to do it!

POSTED BY: Joaquim Nogueira
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract