Yet another interesting number theory question

Q: Let n be an integer not divisble by 3. Suppose that p=n^2+n+1 is a prime and 2^{n+1}\equiv 1 \pmod{p}. Is n a power of 2?

A solution to this problem would imply that every finite flag-transitive projective plane is Desarguesian. Walter Feit obeserved this in his 1990 paper in the Proceedings of the American Mathematical Society, and he confirmed by computer that it is true for n\le    14,400,008. Since then, there has been some review and survey of this problem by various authors, and I’m surprised to see that none have sat at the computer and tried to extend Feit’s computation.

So I gave it a crack myself:

The answer is “Yes” for n \le 30,000,000.

This can definitely be extended by far better programmers than me … any advance on this bound?

9 thoughts on “Yet another interesting number theory question

Add yours

  1. Is there any reason to suspect this is true? Heuristically, one might expect that p=n^2+n+1 is prime with probability 1/2log(n). If p is indeed prime then 2^(n+1) is a n-th root of 1 mod p, which should happen with probability 1/n. So expected number of solutions becomes sum_n (n log n)^(-1), and so one might expect to have C log(log x) solutions n to your system with n at most x.

    Of course a more sophisticated argument may invalidate this heuristic. But my first inclination is that the answer to your question is no, but that a computer search is not guaranteed to find a counterexample, due to the very slow groth of the loglog function.

  2. Heh, that’s the sort of thing I sometime enjoy.

    I got from 0 to 60,000,000 in about *16 seconds* (using 24 cores).
    Here’s the code I’m running:

    I’m output the data for each range of 10^7 values of n in the files in
    the data directory. I’m including multiples of 3 as a sort of
    consistency check on the code and to see if that suggests any other
    structure. Also, I’m using a fairly weak primality test —
    fortunately this is the sort of computation for which that is fine —
    if the test fails then that just means there would be a spurious n in
    our table, so we could double check it later.

    In writing the above… my program got past 400,000,000. I set it
    going for what should take about one day, and go up to 30*10^10 =

      1. This just exceeds the Thas-Zagier computational result in their paper of 2 \times 10^{11}. I should look more closely at your code, but have you used some of the other info such as n\equiv 0\pmod 8? (See Thas and Zagier’s paper for more).

      2. Hi. My code’s completely straightforward (I think), and I didn’t use any extra information. In fact, I even included the n that are divisible by 3. One slightly clever idea is that I use a fast primality test in MPIR (GMP) that could pronounce p prime even though p is composite. That’s fine, since after the fact if this ever happens, one just checks more carefully.

  3. Thanks Sonia; I just realised that Koen and Don had extended the numerical computations, but it seems the folk on this comment list might be able to exceed the bounds they got. I too used sage and easily got up to 4\times 10^7. But I agree with Peter, a solution will be hard to find considering the growth of log(log(x)) (which is an optimistic expected value function).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Up ↑

%d bloggers like this: