Revisions to A bias for runs in Legendre symbols?

added 6 characters in body

Source Link

edited Dec 27, 2022 at 16:40

17.9k
3
45
113

$\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$.

$\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 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$.

$\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$.

`\genfrac`

Source Link

edited Dec 27, 2022 at 0:13

LSpice

12.9k
4
45
69

An$\newcommand\Legendre[2]{\genfrac(){}{}{#1}{#2}}$An odd prime $p$ defines the sequence $\left(\frac{1}{p}\right),\left(\frac{2}{p}\right),\ldots,\left(\frac{p-1}{p}\right)$$\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. NaivelyNaï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,\ldots,10$$1,2,\dotsc,10$.

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

An odd prime $p$ defines the sequence $\left(\frac{1}{p}\right),\left(\frac{2}{p}\right),\ldots,\left(\frac{p-1}{p}\right)$ 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. Naively 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,\ldots,10$.

First occurrences of 'records' have sometimes curious holes: The 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$.

$\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 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$.