Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Hough, Proposition 1, printed pp. 369–371 of the published paper. Use the notation and definitions of goodness and well distribution in the sieve setup.

Statement. For every i≥0i\ge0 and every λ≥0\lambda\ge0, every λ\lambda-good fiber is λ\lambda-well distributed.

Complete proof. Fix a good fiber rr and give Fr=(r mod Qi)⊆Z/Qi+1ZF_r=(r\bmod Q_i)\subseteq\mathbb Z/Q_{i+1}\mathbb Z its uniform probability measure Pr\mathbb P_r. Translation by −r-r and division by QiQ_i identifies it with Z/(Qi+1/Qi)Z\mathbb Z/(Q_{i+1}/Q_i)\mathbb Z. The Chinese remainder theorem decomposes this quotient into independent prime-power coordinates. Each event An,rA_{n,r} depends only on coordinates at primes dividing nn, and

Pr(An,r)=an(r)n.\mathbb P_r(A_{n,r})=\frac{a_n(r)}n.

Thus An,rA_{n,r} is independent of the sigma-algebra of all events with moduli coprime to nn, not merely pairwise independent of those events. In the dependency graph join different n,n′n,n' exactly when gcd⁡(n,n′)>1\gcd(n,n')>1.

If Ni+1=∅\mathcal N_{i+1}=\varnothing, the fiber survives in full. If λ=0\lambda=0, goodness forces every an(r)=0a_n(r)=0: each n>1n>1 has a prime divisor and occurs with a positive coefficient in that prime's sum. Again the full fiber survives. In either case uniform CRT counting gives (4), including λ=0\lambda=0, directly. Hence assume λ>0\lambda>0.

Set xn=eλω(n)an(r)/nx_n=e^{\lambda\omega(n)}a_n(r)/n. For every prime in the band, ∑p∣nxn≤1−e−λ\sum_{p\mid n}x_n\le1-e^{-\lambda}, so 0≤xn≤1−e−λ<10\le x_n\le1-e^{-\lambda}<1. Concavity of log⁡(1−x)\log(1-x) puts its graph above the chord joining x=0x=0 to x=1−e−λx=1-e^{-\lambda}; therefore

1−xn≥exp⁡(−λxn1−e−λ).1-x_n\ge\exp\left(-\frac{\lambda x_n}{1-e^{-\lambda}}\right).

For any n∈Ni+1n\in\mathcal N_{i+1}, repeated factors between 00 and 11 can only decrease a product. Hence

∏n′∈Ni+1(n,n′)>1(1−xn′)≥∏p∣n∏n′∈Ni+1p∣n′(1−xn′)≥e−λω(n).(*)\prod_{\substack{n'\in\mathcal N_{i+1}\\(n,n')>1}}(1-x_{n'}) \ge\prod_{p\mid n}\prod_{\substack{n'\in\mathcal N_{i+1}\\p\mid n'}}(1-x_{n'}) \ge e^{-\lambda\omega(n)}. \tag{*}

The last inequality follows by applying the exponential bound and each prime's goodness condition. Dropping the possible self-factor from the first product only increases it. Multiplication by xnx_n now gives the criterion of the relative local lemma, so the event B=⋂n′An′,rcB=\bigcap_{n'}A_{n',r}^c has positive probability.

Fix b(modn)b\pmod n, and let U={n′∈Ni+1:(n,n′)=1}U=\{n'\in\mathcal N_{i+1}:(n,n')=1\}. The event b(modn)b\pmod n has probability 1/n1/n and is independent of the sigma-algebra generated by (An′,r)n′∈U(A_{n',r})_{n'\in U}. Consequently

Pr(B∩(b mod n))≤1nPr(⋂n′∈UAn′,rc).\mathbb P_r(B\cap(b\bmod n)) \le\frac1n\mathbb P_r\left(\bigcap_{n'\in U}A_{n',r}^c\right).

The relative lemma, including its proved empty-UU case, bounds Pr(B)\mathbb P_r(B) below by the last avoidance probability multiplied by ∏(n,n′)>1(1−xn′)\prod_{(n,n')>1}(1-x_{n'}). Divide the two inequalities and use (*) to obtain Pr(b mod n∣B)≤eλω(n)/n\mathbb P_r(b\bmod n\mid B)\le e^{\lambda\omega(n)}/n. This is precisely (4), and BB is the required surviving fiber.

Source precision. The separate λ=0\lambda=0 argument avoids the printed proof's division by 1−e−λ1-e^{-\lambda} at its stated endpoint. The empty collection and empty relative subcollection are also included.

Bears on. Problem 2.