Timeline for A bias for runs in Legendre symbols?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2022 at 18:06 | comment | added | Christophe Leuridan | @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). | |
| Dec 27, 2022 at 16:40 | history | edited | Roland Bacher | CC BY-SA 4.0 |
added 6 characters in body
|
| Dec 27, 2022 at 16:37 | comment | added | Roland Bacher | @ChristopheLeuridan I agree, see my added comment. The symmetry/antintsymmetry implies that we should expect the longest run to be in a random sequence of length roughly $p/2$ (or slightly longer for $p\equiv 1\pmod 4$ because of symmetry). This decreases the expectation by $1$ which is perhaps too much with respect to the experimental data. | |
| Dec 27, 2022 at 14:13 | comment | added | Christophe Leuridan | 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. | |
| Dec 27, 2022 at 10:50 | comment | added | joro | The first long run is about the first quadratic nonresidue, which is related to RH: mathworld.wolfram.com/QuadraticNonresidue.html | |
| Dec 27, 2022 at 8:14 | comment | added | Roland Bacher | @OfirGorodetsky The bias is about 5 percent for $n=10^5$. | |
| Dec 27, 2022 at 2:37 | comment | added | Ofir Gorodetsky | (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.) | |
| Dec 27, 2022 at 2:30 | comment | added | Ofir Gorodetsky | 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? | |
| Dec 27, 2022 at 0:13 | history | edited | LSpice | CC BY-SA 4.0 |
`\genfrac`
|
| Dec 26, 2022 at 23:39 | history | edited | YCor |
edited tags
|
|
| Dec 26, 2022 at 23:31 | history | edited | Roland Bacher | CC BY-SA 4.0 |
added 263 characters in body
|
| Dec 26, 2022 at 23:03 | history | asked | Roland Bacher | CC BY-SA 4.0 |