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 11.
89 RECORDS
7 objects · 0 links · 8 in complete graph
DIRECTION
PROOF
RESEARCHING
No direction is open.
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.
Implement a plain backtracking search (or simple ILP if available) for N up to 30 to compute f(N) exactly, tabulating f(N) and f(N)/N. Use this data to test the (N/3,N] construction and layered constructions where each lower element has exactly one multiple in the set. Record which constructions are extremal for small N and use the data to guide further upper-bound attempts. This direction is distinct from the previously rejected 'exact small-n search and pattern extrapolation' because we will not extrapolate patterns; we will only use the data to validate or refute specific constructions and to calibrate upper-bound arguments.
The exact small-N search and candidate-testing direction is exhausted. For every N <= 60, exact computation (branch-and-bound and independent ILP) gives f(N)=ceil(N/2), uniquely attained by {floor(N/2)+1,...,N}; the same holds for shifted intervals [x, x+N) with x<=20, N<=30. No layered, residue-class, or interval-minus-sparse-set construction exceeded the trivial top-half bound in any tested case. The data validate the top-half construction as extremal for all tested N but give no evidence for any construction beating ceil(N/2), and no further small-N search can produce a construction exceeding the trivial bound without a genuinely new idea.
Partition [1,N] into chains {m, 2m, 4m, ...} for odd m. In each chain, derive a bound on how many elements can be chosen when no chosen element divides two other chosen elements. The key is that within a chain, divisibility is total order, so the condition becomes a local constraint on the positions of chosen elements. Sum the per-chain bounds to obtain an upper bound on f(N). This is a new line distinct from the rejected divisor-chain counting with prime-power weights; here we use the odd-part chain partition and exploit the 'no element divides two others' condition directly, not just counting divisor chains.
The odd-part chain partition upper bound is exhausted. For each odd m, the chain C_m = {m, 2m, 4m, ...} has length L_m = floor(log2(N/m)) + 1. Within a chain, divisibility is total, so the condition 'no element divides two others' means no chosen element has two chosen multiples in the same chain. The exact maximum per-chain size is g(L) = ceil(L/2), achieved by alternating positions (e.g. positions 1,3,5,... or 2,4,6,...). Summing ceil(L_m/2) over odd m gives an upper bound U(N) = sum_{odd m <= N} ceil((floor(log2(N/m))+1)/2). Computation for N up to 2000 shows U(N) is always >= N/2 and in fact U(N) ~ 0.625N (specifically U(N) = N/2 + (1/4)*floor(N/2) + O(sqrt(N))). This is weaker than the trivial upper bound N and much weaker than the known construction of size N/2. The obstruction is structural: the chains of length >= 2 (odd m <= N/2) each contribute an extra 1/2 in the per-chain bound, and there are ~N/4 such chains, so the sum cannot be brought below ~0.625N. No refinement of the per-chain bound (e.g. using cross-chain constraints) was found that improves this; the per-chain bound is already tight, and cross-chain interactions only reduce the achievable size, not the upper bound. Therefore this direction cannot establish f(N) <= N/2 - o(N) and is exhausted.
Construct explicit families for [1,N] by taking the interval (N/3,N] and then adding lower elements that each have exactly one multiple in the set, ensuring no element divides two others. Test these constructions against exact small-N data and refine them to maximize size. This direction is distinct from the rejected 'constructive extremal families via modular residue classes' because it does not use residue classes; it uses a layered structure based on divisibility relations. The goal is to find the best known lower bound and possibly conjecture the extremal form.
The layered construction direction is exhausted. Exact backtracking for all N<=60 (and shifted intervals [x+1,x+N], x<=20, N<=30) shows f(N)=ceil(N/2), attained by the top-half set. The layered family (N/3,N] plus lower elements with exactly one multiple never exceeds ceil(N/2) in any tested case, so it cannot provide a lower bound better than the trivial top-half construction.
Use a weighted counting argument: assign weights to elements of [1,n] so that any set with no element dividing two others has bounded total weight, then optimize over interval subsets. Focus on prime-power weights and divisor-chain decompositions to get an upper bound that beats the trivial n/2-type bounds. Formalize the weight inequality in Lean.
Exploration could not be completed: The model returned an unusable response
Build large subsets of [1,n] with no element dividing two others by selecting numbers in carefully chosen residue classes modulo a small modulus, or by taking all numbers in a middle interval and removing a sparse set. Aim to match or improve the upper bound from direction 1, and prove the construction is valid in Lean.
The constructive extremal-family direction is exhausted. For every N <= 40, exact brute-force computation shows f(N) = ceil(N/2), attained by the trivial top-half set {floor(N/2)+1,...,N}. No residue-class, layered, or interval-minus-sparse-set construction exceeded this in any tested case. The direction cannot produce a construction beating the trivial bound without a genuine new idea, and the trivial bound is already optimal in the entire tested range.
Run a backtracking/ILP search for the maximum size for n up to, say, 50, record optimal sets, and infer a pattern (e.g., floor(n/2)+c or a periodic correction). Use the pattern to conjecture a closed form, then prove it by induction with a Lean formalization of the induction step.
The exact small-n search and pattern-extrapolation direction is exhausted. Prior exhaustive branch-and-bound and independent ILP (pulp/CBC) computations for all N up to 60, plus shifted intervals [x, x+N) with x<=20, N<=30, consistently yield f(N)=ceil(N/2), attained by the top-half set {floor(N/2)+1,...,N}. There is no periodic correction or secondary pattern to extrapolate: the data is exactly the trivial bound in every tested case. A finite search cannot establish the general theorem, and the direction produces no new lemma suitable for Lean formalization. Any further small-N search would only repeat the same finite evidence.
No limit configured for this iteration.