The Twin Primes Conjecture Gets Solved for Finite Fields | Hacker News Reader

The Twin Primes Conjecture Gets Solved for Finite Fields

wired.com

92 pointsaburan2820 comments

Actual paper: https://arxiv.org/pdf/1808.04001.pdf

How can you prove a conjecture that concerns infinite numbers of primes using a finite number system?

I'm not a mathematician, genuinely curious.

> How can you prove a conjecture that concerns infinite numbers of primes using a finite number system?

Your intuition is correct, but doesn't go far enough! In fact, the notion of a prime in general doesn't make much sense (in Galois fields) :)

The article explains it fairly well. Basically, what was proved was the fact that there exist an infinite number of twin prime polynomials (i.e. polynomials that cannot be factored and differ by a fixed gap) in finite number systems.

An interesting aside is that the encryption system most of us rely on every day, AES, relies on a prime over a finite (Galois) field 2^8. The "subbytes" step is a one to one mapping of a byte to another byte, and it's defined in terms of a prime polynomial in the field GF(2^8). In practice though, the table is pre-computed and hardcoded into AES implementations.

> In practice though, the table is pre-computed and hardcoded into AES implementations.

It's often referred to as the "s_box" and the "reverse s_box" (for de-encryption).

Unless Galois Fields doesn't refer to the more specific 'field' class of object, why wouldn't primes make sense in that context? Fields can have divisors. You can define a prime as any number whose only divisor is itself and one.

I'm out of practice, so maybe you're staying that because you'd essentially have prime equivalence classes that the meaning is different?

If you want a general definition of prime, you would say that a prime is an element p which p|a*b implies p|a or p|b, with the additional restriction that p|1 is false (such elements are called “units”). This lets you extend the notion of “prime” to rings in general, including objects like polynomials or matrixes.

If you are curious about some of the details, we can add that “prime” is not quite the same as “irreducible”, although the prime elements and irreducible elements are the same in the more familiar rings.

The reason why “prime” doesn’t make much sense in Galois fields is precisely because it’s a field—technically, there are no primes in Galois fields, because every nonzero element divides 1, therefore every nonzero element is a unit, therefore not a prime. So there are no primes in Galois fields. This is mentioned in the article.

Even if the number field is finite, there are an infinite number of polynomials for it. For example the finite field F2 has two elements {0, 1} but an infinite number of polynomials 0, 1, x, x + 1, x^2, x^2 + x + 1, x^2 + 1, «x^2 + x, and on and on. Some of these have nontrivial factors (x^2 + x = x(x+1)) and some don't (x^2 + x + 1 has no factors beyond itself and 1).

(The other answer to your question is more complete but also a bit more advanced, figured this was worth surfacing.)

This is not correct, there are a finite number of polynomials for any finite field. This is using the usual definition for polynomial equivalence, where two polynomials are equal if they take the same values over all points in the domain.

You are talking about the polynomial ring, which is not a field.

The finite field F2 has four polynomials: 0, 1, x, and x+1. Other polynomials do not exist, because x^2=x.

It might help if you explain what is meant by F2.

As far as I can tell you're referring to the integer finite field containing the values {0, 1}.

  2 % 2 = 0
  3 % 2 = 1
  x^n % 2 = x
  2x % 2 = 0
  (2n + 1)x % 2 = x

So there are no (distinct) constants other than 0 or 1 and no multiples or exponents of x other than 1.

These facts might be obvious to someone who understands the jargon and theory of the mathematics in question, but probably need a bit more clarity when the target is the general populace.

Appreciate what you're saying, but the linked paper is talking about results in F_p[T], the polynomial ring.

Generally given a polynomial in R[x], you want to be able to evaluate it not just when x is in R, but when it's in any R-algebra. So we wouldn't automatically identify x^2 and x.

There is a wide-ranging set of analogies around the (inherently paradoxical) idea of the "field with one element", one of which is that the integers are expected to behave like the ring of polynomials over a field with one element. Another example is that the symmetric group on n elements is expected to behave like the group of invertible n x n matrices. See this page for a fairly full list of examples: https://ncatlab.org/nlab/show/field+with+one+element

Isn’t (the unique finite semifield which isn’t also a field) adjoin x, the same as the integers (but, with the addition on the integers being the “multiplication” on this thing)?

Integers and polynomials with coefficients from a finite field almost the same thing. For example, the number 2019 can be expressed as 2 * 10^3 + 0 * 10^2 + 1 * 10^1 + 9 * 10^0, or 2x^3 + x^1 + 9x^0 where x=10. Number is a special case of a polynomial with a coefficients from a finite field.

They are different things really, but close enough to have much in common.

upd. formatting

There’s a minor problem here, since the coefficients aren’t being taken from a finite field (the digits 0..9 don’t form a finite field).

There is a bigger problem. If you keep adding 1 you only get all the elements for the integers.

One classical method is to show that if some property holds in infinite object, same or related thing must also hold for some (or all) large enough finite objects.

Consider for example Grothendieck-Ax theorem: if f: C^n -> C^n is an injective (that is, one-to-one) multiple variable polynomial function over complex numbers, then it's also surjective. One of the ways to prove it is to show via model theory magic that if there was a counterexample to this theorem, there would also be a counterexample g: F^n -> F^n, where F is some finite field. But an injective function from finite set to finite set of the same size is also surjective.

Is this of interest (so far) only to mathematicians, or does it have applications in other fields (crypto?).

"Is there a cryptography application" was my thought too, however I'm guessing pairs of primes aren't used there.

Reply on news.ycombinator.com