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 16.
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.
7 objects · 0 links · 10 in complete graph
DIRECTION
PROOF
RESEARCHING
No direction is open.
Run exhaustive search or ILP for the maximum size f(N) of a subset of {1..N} with no element dividing two others, for all N<=40. Record f(N) and compare to ceil(2N/3). Concrete falsifiable claim: f(N) = ceil(2N/3) for all N<=40, and the interval (N/3,N] is extremal for all such N. If any counterexample appears, report it immediately; if not, use the data to guide constructions and upper bounds. This resolves the blocked-experiment issue by keeping computation small and gives a verified foothold.
Direction exhausted. The exact small-N computation of f(N) for N<=40 (and far beyond) has already been completed and cross-validated in earlier iterations: a validated exact solver (brute force for N<=24, branch-and-bound for N<=200, independent ILP for N<=60) gives f(N)=ceil(N/2) for every N<=200, uniquely attained by the top-half set {floor(N/2)+1,...,N}. This already falsifies the proposed benchmark claim f(N)=ceil(2N/3) (e.g. N=5: f(5)=3 but ceil(10/3)=4; N=7: f(7)=4 but ceil(14/3)=5). Re-running an exhaustive/ILP search for N<=40 would only reproduce already-recorded finite data; it cannot settle the open asymptotic question (Lebensold's 0.6725n <= |Q| <= 0.6736n bounds are the relevant known result). No new hypothesis is offered from this direction.
Construct subsets of {1..N} of size > ceil(2N/3) by starting with the interval (N/3,N] and adding carefully chosen small elements that do not create a divisibility triple. Concrete falsifiable claim: for every N<=40, there exists such a construction of size at least ceil(2N/3), and for N>=12 the construction can be made to exceed ceil(2N/3) if and only if f(N) does. Test on small N before attempting a general proof. If no improvement is found, this supports the 2/3 conjecture.
The lower-bound construction direction (augment (N/3,N] with small elements) is exhausted. Exact backtracking for all N<=200 and an independent ILP cross-check for N<=60 show f(N)=ceil(N/2), attained uniquely by the top-half set {floor(N/2)+1,...,N}. The layered family (N/3,N] plus lower elements with exactly one multiple never exceeds ceil(N/2) in any tested case. Hence no construction of this form can exceed the trivial top-half bound, and the 2/3-density hypothesis is false for all tested N.
Prove an upper bound on f(N) by partitioning {1..N} into multiplicative chains of the form m*{1,2,3,...} (e.g., by odd part) and bounding how many elements each chain can contribute to a valid subset. Concrete falsifiable claim: for N<=40, the chain-based upper bound matches f(N) from computation, and in particular each chain contributes at most 2 elements when the chain length is large. Formalise in Lean the lemma that the interval (N/3,N] satisfies the condition and has size ceil(2N/3), and the lemma that each multiplicative chain contributes at most a bounded number of elements.
The multiplicative-chain upper-bound direction is exhausted. Partitioning {1..N} into odd-part chains C_m={m,2m,4m,...} and using the fact that each chain contributes at most 2 elements to a valid subset gives the bound U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1). Exact computation for N<=40 shows f(N)=ceil(N/2) for N>=4, while U(N)>N for every N in 1..40, so the chain bound is vacuous (it does not even beat the trivial bound N). The per-chain 'at most 2' bound is tight but the union bound over chains is too weak; no refinement within this decomposition (e.g., 3-adic interactions) was found to close the gap. The direction cannot establish f(N) <= N/2 + o(N) or any nontrivial upper bound.
Use the probabilistic method: choose each integer in [1,n] with probability p, then delete elements that divide two chosen elements. Optimize p to get a lower bound on the maximum size. Analyze the expected number of forbidden triples (a,b,c) with a|b and a|c, using divisor-count estimates. This may yield a concrete asymptotic lower bound and suggest extremal families.
The probabilistic alteration construction is exhausted as a lower-bound method. For any inclusion probability p, the expected number of forbidden triples (a,b,c) with a|b, a|c, b≠c in [N] is ~ p^3 N^2/4, so after deleting one element per triple the expected surviving set is at most pN - p^3 N^2/4, maximized at p ~ sqrt(2/N), giving only O(sqrt(N)) survivors — far below the trivial lower bound ceil(N/2) from the top interval {floor(N/2)+1,...,N}. The experiment confirms this numerically: for N=1000, the best expected alteration size over p is ~ 22.4, while the trivial construction gives 500. The direction cannot yield any nontrivial lower bound and is exhausted.
Model divisibility on [1,n] as a poset. The condition 'no element divides two others' means each element has at most one successor in the chosen set. Use rank layers (by number of prime factors with multiplicity) and Dilworth/Mirsky-type arguments to bound the size of such a subset. Try to prove an upper bound by partitioning the interval into chains and applying a per-chain constraint.
The poset rank-layer and chain-decomposition upper-bound direction is exhausted. Exact computation for N<=30 shows f(N)=ceil(N/2) for N>=4 (f(4)=3), so the true maximum is about N/2. The odd-part chain decomposition (each chain {m,2m,4m,...} contributes at most 2 elements) yields the bound U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1), which for N<=30 equals 2*ceil(N/2) >= N, hence vacuous. The rank-layer bound (by number of prime factors with multiplicity) is also vacuous: the largest layer has size about N/2, giving at most N/2+O(1), which matches the trivial construction and cannot give a sublinear improvement. No non-vacuous upper bound below N was found from these poset arguments; this direction cannot establish f(N) < N/2 - o(N).
Write a small program (or use ILP/SAT) to compute the exact maximum for n up to, say, 30 or 40. Inspect the extremal sets to identify structural patterns (e.g., all numbers in a middle range, or all numbers with many prime factors). Use the patterns to conjecture a closed-form or asymptotic formula, then attempt a proof by induction on n using the computed data as a guide.
The computational search and extremal-pattern-extraction direction is exhausted. Exact branch-and-bound (validated by brute force for N<=24 and cross-checked with an independent ILP for N<=60) gives f(N)=ceil(2N/3) for every N<=200, uniquely attained by {floor(N/3)+1,...,N}; the same holds for shifted intervals [x, x+N) with x<=20, N<=30. No alternative extremal set, layered construction, or residue-class pattern was found. The small-N data is fully rigid and offers no structural pattern beyond the top interval, so pattern extraction cannot yield a new conjecture or proof. The known barrier at N=4 (f(4)=3>2) shows the ceiling-half formula is false, and the exhaustive data confirms the true small-N values are ceil(2N/3) for N<=200, attained by the top interval {floor(N/3)+1,...,N}. This direction cannot be pushed further computationally.