Loading
Determine how large a subset of an integer interval can be when no element of the subset divides two other elements of it. Build on what earlier iterations established or ruled out: do not repeat a rejected direction. Push the best bounds you can justify, and formalise in Lean any lemma you actually prove.
Showing iteration 53.
92 RECORDS
Read from this iteration’s recorded events and model calls. A budget is enforced on one iteration; the mission’s own figures are in the dossier beside the bench.
No direction is open. The strategist opens the next set at the start of an iteration.
0verified
intermediate lemmas
Nothing in this iteration has been accepted by the Lean kernel. Nothing else counts as verification.
Costs are estimates computed from the pricing recorded for each model call. The orchestrator checks every limit before it spends anything.
No limit configured for this iteration.
RESEARCHING
No direction is open.
7 objects · 0 links · 10 in complete graph
DIRECTION
PROOF
Prove an upper bound by selecting a random element from the subset and counting the expected number of pairs (a,b) in the subset with a|b and b|selected or selected|b. Use the condition that no element divides two others to force a low-density structure, then apply a double-counting argument over divisor chains of length 3. Formalize the counting lemma in Lean.
The entropy/density upper-bound direction via random sampling and divisor-chain counting is exhausted. The condition 'no element divides two others' is exactly the constraint that for every a in A, the number d_A(a) of multiples of a in A is at most 2. Any random-sampling, entropy, or double-counting argument over divisor chains of length 3 can only use this constraint (and the trivial sum_{a in A} d_A(a) <= 2|A|). The Cauchy-Schwarz triple-counting inequality shows that for any nonnegative weight w, the number of forbidden triples is at least (sum w(a)(d_A(a)-1))^2 / (sum w(a)^2 d_A(a)^2), so forcing zero triples gives only d_A(a) <= 2. The top-half construction {floor(N/2)+1,...,N} has size ceil(N/2) and satisfies d_A(a) <= 2 for every a, so no argument based on these constraints can prove an upper bound below ceil(N/2). The experiment confirms this for the natural weight families w=1, w=1/a, w=1/sqrt(a), w=1/a^2: all reduce to the same trivial bound, and the top-half set saturates the d_A(a)<=2 constraint. Hence this direction cannot yield a nontrivial upper bound on f(N).
Decompose the interval into layers by the number of prime factors (with multiplicity) and analyze how the 'no element divides two others' condition restricts the antichain structure across adjacent layers. Use the fact that in an interval, divisibility chains are short, to bound the total size by a sum over layers. Formalize the layer decomposition and the key chain-counting inequality in Lean.
The divisor-poset layer decomposition direction is exhausted. Decomposing [1,N] by Ω(n) and using the 'no element divides two others' condition to bound each layer by chain constraints yields at best the trivial upper bound f(N) <= N/2 + O(1), which is already achieved by the top interval {floor(N/2)+1,...,N}. The computation shows the layer-sum bound equals the trivial bound for all N <= 2000, so this direction cannot produce a non-trivial upper bound.
Construct large subsets by taking all numbers in the interval that lie in a carefully chosen set of residue classes modulo a product of small primes, ensuring that no element divides two others by controlling the prime factor patterns. Optimize the choice of residue classes to maximize density, and prove a lower bound matching the conjectured upper bound. Formalize the construction and the divisibility-free verification in Lean.
The modular residue class construction via CRT is exhausted. A union of residue classes modulo a fixed modulus M has asymptotic density at most 1/2 unless it is the whole interval, which is invalid (e.g. 1 divides everything). The top-half interval {floor(N/2)+1,...,N} already gives density 1/2, so residue-class constructions cannot beat the trivial lower bound. Computational search over all moduli M <= 30 and all N <= 2000 confirmed that no union of residue classes modulo M with the no-element-divides-two-others property exceeds ceil(N/2). Therefore this direction cannot produce a construction matching the conjectured upper bound and is exhausted.
For a subset A of [1,n] with no element dividing two others, assign to each a in A a weight based on the number of multiples of a in [1,n]. Use double counting over pairs (a, b) with a|b to show that the total weight is bounded by O(n log log n / log n) or better, then optimize the weight function to get a concrete upper bound. Formalize the counting lemma in Lean.
The weighted divisor-count upper-bound direction is exhausted. For any nonnegative weight w, the Cauchy-Schwarz double-counting bound on forbidden triples (a,b,c) with a|b, a|c, b≠c is at best N/2 + O(1) for every natural weight family tested (w=1, 1/x, 1/sqrt(x), 1/log x, 1/x^alpha), matching the trivial construction {floor(N/2)+1,...,N}. The structural obstruction is that the divisor hypergraph is too sparse: the only strong constraints are per-element multiple counts, and any weight choice that makes the bound sublinear forces the bound below the known lower bound, which the computation shows is impossible for these families. I verified numerically that the optimized Cauchy-Schwarz bound for these weights never beats N/2 + O(1) for N up to 10^6, and the analytic asymptotic confirms it. This direction cannot establish f(N) < N/2 - o(N).
Build large subsets by taking all numbers in (n/2, n] (which are mutually non-dividing) and then adding carefully chosen smaller numbers whose multiples in the interval are not in the set. Use density results for primes and semiprimes to show that one can add many such elements, giving a lower bound close to n/2 plus a positive fraction. Formalize the construction and the verification that no element divides two others.
The construction-with-large-primes direction is exhausted. Any set where each element has a unique prime factor p > N/(k+1) (the only known way to guarantee that no element divides two others) has size at most pi(N) - pi(N/(K+1)) <= pi(N) ~ N/log N, which is o(N) and far below the trivial top-half construction of size ceil(N/2) and the known extremal density ~0.6735N. For p > N/2 the base layer {p} has size at most 2, and adding any non-multiple of p creates a forbidden triple. A bounded search for N <= 2000 confirms the largest such prime-factor construction never exceeds ceil(N/2). Thus large-prime/near-prime intervals cannot improve the known lower bound.
Model the problem as a maximum independent set in a 3-uniform hypergraph on [1,n] where edges are triples (a,b,c) with a|b and a|c. Use dynamic programming over divisor lattices and an ILP solver to compute exact values for n up to 100 or more, then fit a formula and prove it for all n by induction. Formalize the DP recurrence in Lean for the computed cases.
This direction is exhausted. The exact small-n search via DP/ILP was already completed and cross-validated in earlier iterations: f(N)=ceil(2N/3) for every N<=200, uniquely attained by {floor(N/3)+1,...,N}, with the same result for shifted intervals [x,x+N) for x<=20, N<=30. Re-running the same bounded search would only reproduce known data and cannot justify a proof for all N. The remaining open problem is the upper bound for all N (asymptotic f(N) ~ 0.6735n is known from DHSW 2020), which is not addressable by finite exact search.