[seqfan] A097160

[Don Reble]

> %I A097160
> %S 5,17,53,193,457,2153,4481,9857,17041,23473
> %N Greatest prime p such that there are n, but not n+1, consecutive
>    quadratic residues mod p, or -1 if no such prime exists.
> %C It is not clear to me how many of these entries have been proved to
>    be correct.  As the following comments by David Harden show, this
>    is a difficult problem. - njas, Jan 01 2007

    I should have investigated further, back then:
    a(9)=17041 is wrong (it's >= 25793)
    a(10)=23473 is wrong (it's >= 60961)

    The sequence is total:

> According to a theorem of Alfred Brauer [1] all sufficiently large
> primes have runs of L consecutive integers that are Kth power residues,
> where K and L are arbitrarily given integers.
    That quote is from [2].

    David Harden's proof (that a(2)=17) looks hard to generalize:
    there's no upper bound on the first run of three [2], and so
    he uses arithmetic progressions of three squares. But there is
    no progression of four squares!

    [1] Alfred Brauer, Ueber Sequenzen von Potenzresten,
        S.-B. Deutsch. Akad. Wiss. Berlin 1928, 9-16.
    [2] D. H. Lehmer and Emma Lehmer, On Runs of Residues,
        Proc. Amer. Math. Soc, vol 13, 1962, pp 102-106.

    But you don't need progressions of squares, just of quadratic
    residues. Exploiting that, I find another proof for A097160(2).
    Assuming that there are no three consecutives:

         5-  (1+ 5- 9+) / 4+
         7-  (7- 16+ 25+) / 9+
        20-  (4+ 20- 36+) / 16+
        35+  5- * 7-
        34-  (34- 35+ 36+) / 1+
        27+  (20- 27+ 34-) / 7-
         3+  27+ / 9+
         2-  (1+ 2- 3+) / 1+
        10+  2- * 5-
        11-  (9+ 10+ 11-) / 1+
        13-  (10+ 13- 16+) / 3+
        15-  3+ * 5-
        15+  (11- 13- 15+) / 2-

    Meanings:
    5 is a non-residue, so that (1/4, 5/4, 9/4) isn't a run of residues.
    ...
    35 is a residue, because it's the product of non-residues 5 and 7.
    ...
    3 is a residue, because it's the quotient of residues 27 and 9.

    That contradiction (15-, 15+) refutes the assumption.

    This also assumes that the modulus is prime (so that products of
    non-residues are residues), and that each prime factor of the
    mentioned numbers does not divide the modulus (so that each number
    isn't congruent to 0, and therefore is a residue or a non-residue,
    and is invertible).
    The mentioned numbers are 2 3 4 5 7 9 10 11 13 15 16 20 25 27 34 35 36;
    their prime factors are 2 3 5 7 11 13 17;
    and so the proof applies only to prime moduli > 17.
    So A097160(2) <= 17.

    Similarly, I find that
        a(3) <= 107
        a(4) <= 449
        a(5) <= 1987
        a(6) <= 12919
    (Perhaps there are proofs which provide lower upper-bounds;
    my program stops when it finds any ol' proof.)
    The rest (a(2)=17, a(3)=53, a(4)=193...) is just computation.

    Anyway, the sequence is correct to
        5,17,53,193,457,2153
    and it very likely continues
        4481,9857,25793,60961,132113,324673

    I agree that it's a hard problem: my proof for a(6) has about
    660,000 lines. And there's no reason to think that my procedure
    always finds a proof, or always halts.

    Unless, of course, there is. [1] seems to be inaccessible to me,
    physically and also (I presume) linguistically. Does Brauer have
    a computable upper bound?

-- 
Don Reble  djr at nk.ca


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.