Skip to content

Yet another interesting number theory question

May 16, 2011

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 Comments leave one →
  1. May 17, 2011 1:51 am

    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. May 17, 2011 3:25 am

    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 =

    • May 18, 2011 1:42 am

      My calculation completed up to 3*10^11, found no new examples, and took 22.38 hours walltime (hence probably about 20 days CPU time).

      • May 19, 2011 8:26 am

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

      • May 19, 2011 2:24 pm

        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.

      • May 22, 2011 6:15 am


        I pushed my computation up to 10^12 (instead of merely 3*10^11). I found no new examples.

        — William

  3. May 17, 2011 5:25 am

    A short program in Sage indicates the answer to the question is “yes” for $n <= 1,000,000,000$.

  4. May 17, 2011 7:47 am

    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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: