The Twin Primes Conjecture Gets Solved for Finite Fields

https://www.wired.com/story/a-big-question-about-prime-numbers-gets-a-partial-answer/

by aburan28 • 7 years ago

92 20 7 years ago

wired.com

umvi• 7 years ago

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

I'm not a mathematician, genuinely curious.

dvt2• 7 years ago

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.

AaronFriel• 7 years ago

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.

eximius• 7 years ago

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?

tildedave2• 7 years ago

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

klodolph3• 7 years ago

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.

cwzwarich• 7 years ago

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

drdeca• 7 years ago

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

ordu• 7 years ago

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

klodolph3• 7 years ago

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

xyzzyz• 7 years ago

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.

dvt2• 7 years ago

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

Jeff_Brown• 7 years ago

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

kristianp• 7 years ago

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

The Twin Primes Conjecture Gets Solved for Finite Fields

Related Stories