Wiki
Wiki

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

Updated


The complete source chain uses the following external results. Their exact interfaces and applications are recorded here; their proofs are outside this source unit.

  1. Frankl--Wilson forbidden-intersection bound. The exact form is Theorem 2: when kk is a prime power and n=4kn=4k, a family of n/2n/2-subsets of [n][n] with no distinct pair intersecting in n/4n/4 elements has size at most 2(n−1n/4−1)2\binom{n-1}{n/4-1}. Kahn and Kalai state and attribute this result on physical PDF p. 2 (journal p. 61). The original 1981 proof has not been recursively checked here.

  2. Stirling's formula. As n→∞n\to\infty through positive integers,

n!=2πn (n/e)n(1+o(1)).n!=\sqrt{2\pi n}\,(n/e)^n(1+o(1)).

The proof uses only its fixed-density binomial consequence

log⁡(nαn)=nH(α)+O(log⁡n),H(α)=−αlog⁡α−(1−α)log⁡(1−α),\log\binom n{\alpha n}=nH(\alpha)+O(\log n), \qquad H(\alpha)=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha),

for α=1/2\alpha=1/2 and 1/41/4 along multiples of four.

  1. Prime number theorem. The form used is the consequence that if p(x)p(x) is the largest prime at most xx, then p(x)/x→1p(x)/x\to1 as x→∞x\to\infty. Equivalently, for every ε>0\varepsilon>0, every sufficiently large xx has a prime in [(1−ε)x,x][(1-\varepsilon)x,x]. Kahn and Kalai explicitly invoke the prime number theorem in the last sentence of Section 2 on physical PDF p. 2.

The incidence-vector distance calculation, the affine-dimension bound, the binomial simplification, monotonicity under Euclidean embedding, and the conversion from covers of a finite configuration to partitions are proved directly in this source chain and require no further imported theorem.