That’s the same heuristic argument I was imagining for why it would be Poisson (except I wasn’t being careful and thinking about CRT, or explicitly cutting out the large primes, just naively assuming independence by default). When mean and variance are equal, isn’t a Poisson distribution extremely close to a normal distribution? Or put differently: if you are adding up coins whose probability of heads is close to 0, I’d expect the poisson approximation to be as good as the normal approximation. There are higher-order differences between the two distributions, but is it specifically known to be more normal than Poisson?
I guess the big problem is that you need an extremely accurate approximation to get at the parity, and neither of these approximations is very accurate? E.g. adding 1 is a pretty small impact on the distribution, but a huge impact on the parity.
Another pass at the heuristic argument:
The number of copies of a prime p that divides x is geometric. The probability that the count is odd is 1p+1. I’d guess these events are all pretty independent for p<x1/4 based on what you said.
If we have a bunch of coins with probability 1p+1 of being odd, the probability of the sum being even is 12+12∏(1−2p+1)
That’s a bias of order 1log(x)2 again.
So it seems like the count of small prime divisors should have a very significant bias towards being even.
So I guess all the action is in the large prime divisors, and probably from the anticorrelation with the count of small prime divisors (seems like the magic is that 0 isn’t a valid answer). I guess we kind of knew that anyway, since it’s going to flip the sign of the bias. In expectation there are O(1) large prime divisors, but that’s still enough to totally dominate the calculus.
This doesn’t feel like a promising line of attack. Would be interesting to check the claim that the count of small prime divisors with multiplicities is quite even-skewed.
I agree with all of that, and I think if you simulated it you’d indeed find a large bias for the number of small prime divisors to be even. The problem is 1/log(x)2 is such a small bias in expectation that it will already be offset by just the primes in the interval [x,2x] which contributes on the order of ∼1/logx to the average in the opposite direction, since all primes trivially have an odd number of divisors.
Furthermore, there are subtleties here about exactly how much independence you need. If you want everything to be jointly independent then you can really only work with the primes up to logx while being safe—this is because the product of the primes up to x is roughly of order ex. Once you go past that, while correlations involving only a small number of primes are still fine, correlations involving lots of primes break down, and for parity problems you need to control the entire joint distribution in a fine way.
This is not a problem for the normal approximation because to show convergence in distribution to a normal distribution, you just need to show all the moments converge to the right values and use a result like Stone-Weierstrass to approximate any continuous test function uniformly by a polynomial. You can do this just by working with primes up to xα for α depending on the exact moment you’re studying. However, this result is really “low resolution”, as you correctly identify.
That’s the same heuristic argument I was imagining for why it would be Poisson (except I wasn’t being careful and thinking about CRT, or explicitly cutting out the large primes, just naively assuming independence by default). When mean and variance are equal, isn’t a Poisson distribution extremely close to a normal distribution? Or put differently: if you are adding up coins whose probability of heads is close to 0, I’d expect the poisson approximation to be as good as the normal approximation. There are higher-order differences between the two distributions, but is it specifically known to be more normal than Poisson?
I guess the big problem is that you need an extremely accurate approximation to get at the parity, and neither of these approximations is very accurate? E.g. adding 1 is a pretty small impact on the distribution, but a huge impact on the parity.
Another pass at the heuristic argument:
The number of copies of a prime p that divides x is geometric. The probability that the count is odd is 1p+1. I’d guess these events are all pretty independent for p<x1/4 based on what you said.
If we have a bunch of coins with probability 1p+1 of being odd, the probability of the sum being even is 12+12∏(1−2p+1)
That’s a bias of order 1log(x)2 again.
So it seems like the count of small prime divisors should have a very significant bias towards being even.
So I guess all the action is in the large prime divisors, and probably from the anticorrelation with the count of small prime divisors (seems like the magic is that 0 isn’t a valid answer). I guess we kind of knew that anyway, since it’s going to flip the sign of the bias. In expectation there are O(1) large prime divisors, but that’s still enough to totally dominate the calculus.
This doesn’t feel like a promising line of attack. Would be interesting to check the claim that the count of small prime divisors with multiplicities is quite even-skewed.
I agree with all of that, and I think if you simulated it you’d indeed find a large bias for the number of small prime divisors to be even. The problem is 1/log(x)2 is such a small bias in expectation that it will already be offset by just the primes in the interval [x,2x] which contributes on the order of ∼1/logx to the average in the opposite direction, since all primes trivially have an odd number of divisors.
Furthermore, there are subtleties here about exactly how much independence you need. If you want everything to be jointly independent then you can really only work with the primes up to logx while being safe—this is because the product of the primes up to x is roughly of order ex. Once you go past that, while correlations involving only a small number of primes are still fine, correlations involving lots of primes break down, and for parity problems you need to control the entire joint distribution in a fine way.
This is not a problem for the normal approximation because to show convergence in distribution to a normal distribution, you just need to show all the moments converge to the right values and use a result like Stone-Weierstrass to approximate any continuous test function uniformly by a polynomial. You can do this just by working with primes up to xα for α depending on the exact moment you’re studying. However, this result is really “low resolution”, as you correctly identify.