6
$\begingroup$

$\newcommand\Legendre[2]{\genfrac(){}{}{#1}{#2}}$An odd prime $p$ defines the sequence $\Legendre1 p,\Legendre2 p,\dotsc,\Legendre{p-1}p$ of values of the Legendre symbol describing the quadratic nature of integers modulo $p$. We denote by $R(p)$ the longest run (largest subset of consecutive squares or of consecutive non-squares modulo $p$) of this sequence. Naïvely assuming the sequence to be similar to a sequence of $p-1$ tosses of a fair coin, we should expect $R(p)$ to be of size $\log(p-1)/\log(2)$. Since $\log(p)$ is the mean distance between $p$ and the following (or previous) prime, we should have $$\frac{\log(2)}{n}\sum_{p\leq n}R(p)\longrightarrow 1$$ (where the sum is over all odd primes $\leq n$) for $n\rightarrow \infty$.

This seems to be more or less the case numerically albeit the quantity $\frac{\log(2)}{n}\sum_{p\leq n}R(p)$ is strictly smaller than $1$ for the first few thousand initial values of $n$. This indicates a very slight bias for these sequences of Legendre symbols.

Is this an artefact?

(Added: A possible explanation is the symmetry/antisymmetry of the Legendre symbol showing that we are sort of working with a random sequence of length $(p-1)/2$. This 'explanation' leads however to the opposite problem: The sum is too large, I believe.)

A few complements: The set of primes with a given value of the longest run should be finite. Computations for primes up to $50000$ suggest the cardinalities $$1,2,2,8,6,27,30,70,125,254$$ for the sets of odd primes giving rise to longest runs of length $1,2,\dotsc,10$.

First occurrences of 'records' have sometimes curious holes: The first few smallest primes with maximal runs of length $29$ are smaller than the smallest primes with maximal runs of length $25$, $26$, $27$ or $28$.

Improve this question
$\endgroup$
7
  • $\begingroup$ This could be simply due to $n$ overestimating the sum $\sum_{p\le n}\log p$. Indeed, it is known that the logarithmic integral overestimates the number of primes up to $n$ for all $n$ up to a ridiculously high number (look up Skewes' number), and the same should be true here. How large is your bias? $\endgroup$
    – Ofir Gorodetsky
    Commented Dec 27, 2022 at 2:30
  • $\begingroup$ (To eliminate this issue, you can normalize by $\sum_{p\le n}\log(p-1)/\log(2)$. And maybe work only with primes in $[n/2,n]$ to avoid small primes.) $\endgroup$
    – Ofir Gorodetsky
    Commented Dec 27, 2022 at 2:37
  • $\begingroup$ @OfirGorodetsky The bias is about 5 percent for $n=10^5$. $\endgroup$
    – Roland Bacher
    Commented Dec 27, 2022 at 8:14
  • 2
    $\begingroup$ In the set $\{1,\ldots,p-1\}$, there are as many squares modulo $p$ as non-squares modulo $p$. This perfect parity between squares and non-squares should reduce the probability of long runs, compared with a sequence of independent uniform signs. I think it may explain the bias observed. To confirm this intuition, one should compare the sequence of Legendre symbols with a sequence of signs chosen uniformly among all sequences of signs having exactly $(p-1)/2$ plus and $(p-1)/2$ minus. $\endgroup$
    – Christophe Leuridan
    Commented Dec 27, 2022 at 14:13
  • 1
    $\begingroup$ @Roland Bacher The antisymmetry when $p \equiv 3 [4]$ forces the parity between squares and non-squares. But when $p \equiv 1 [4]$, parity between squares and non-squares is not implied by the symmetry, and reduces strongly the probability of runs with length $\ge p^{3/4}$ (for example). $\endgroup$
    – Christophe Leuridan
    Commented Dec 27, 2022 at 18:06

0

Reset to default

You must log in to answer this question.