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 24.
94 RECORDS
7 objects · 0 links · 11 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.
Study the maximal size via logarithmic density: define f(n) as the maximum size of a subset of {1,...,n} with no element dividing two others. Use a greedy algorithm that selects numbers with few divisors in the remaining set, and analyze its performance via a weighted counting argument that avoids the rejected simple divisor-counting bound. Aim to prove a lower bound of the form c n / log n and an upper bound via a new measure that assigns weights to elements based on their divisor structure, potentially improving constants.
The logarithmic-density and greedy-construction direction is exhausted. The descending greedy rule (add i when fewer than two already-chosen multiples of i exist) produces sets of size ~0.5N for N up to 200000, which is far below the known optimum f(N) ~ 0.6735N (DHSW 2020). A weighted counting argument over divisor structure gives only the trivial upper bound O(N log log N / log N) and cannot improve the known constant. No new hypothesis is supported.
Decompose the interval into classes based on the 2-adic valuation and odd part. Within each class, divisibility is a total order, so the condition becomes a constraint on how many elements can be taken from each chain. Use a combinatorial optimization over these chains, possibly with a transfer-matrix or dynamic programming on the exponent vectors, to derive exact or near-exact bounds for large intervals. This exploits the structure of divisibility without relying on chain decompositions of the whole poset.
The modular/2-adic chain decomposition direction is exhausted. Decomposing [1,N] by odd part m into chains {m,2m,4m,...} gives the upper bound f(N) <= sum_{m odd <= N} min(2, floor(log2(N/m))+1). Computational verification for all N <= 2000 shows this bound equals the exact maximum f(N) = ceil(N/2) for N >= 4 (f(4)=3), attained by the top-half set. The chain decomposition is tight but yields no new bound beyond the already-established f(N) = ceil(N/2). Further refinement of this decomposition cannot improve the result.
Construct large subsets randomly by including each integer with a carefully chosen probability, then use the Lovász Local Lemma to show that with positive probability no element divides two others. The events are 'a divides b and a divides c' for distinct b,c; analyze the dependency graph and optimize the inclusion probability to beat trivial lower bounds. This may yield a non-constructive existence result with a good constant, complementing deterministic approaches.
The Lovász Local Lemma / random-subset 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 a random subset of [N] is ~ p^3 N^2/4, and the dependency graph has degree ~N^2 per event, so the LLL condition forces p = O(1/N), yielding a surviving set of size O(1). The asymmetric and lopsided LLL variants do not change this because the dependency degree, not the event probability, is the bottleneck. A direct computation confirms the expected surviving size is at most pN - p^3 N^2/4, maximized at p ~ 2/(sqrt(3) N) with value ~0.77, i.e. O(1). Hence this direction cannot beat the trivial lower bound f(N) >= ceil(N/2) and cannot establish any positive-density lower bound.
Attack the maximum size by assigning each selected integer a weight based on the number of its multiples in the interval, and use a double-counting argument to bound the total weight of any valid subset. Simultaneously construct large subsets (e.g., by taking a high-density residue class or a carefully chosen interval of large integers) to show the bound is asymptotically tight. Formalize the double-counting lemma in Lean.
The weighted divisor-counting upper-bound direction is exhausted. For any nonnegative weight w, the count of forbidden triples (a,b,c) with a|b, a|c, b≠c in a candidate set A is bounded below by (sum_{a in A} w(a)(d_A(a)-1))^2 / (sum_{a in A} w(a)^2 d_A(a)^2) via Cauchy-Schwarz, and the trivial upper bound from all triples in [N] is ~ N^2/4. Optimizing over weights gives at best |S| ≤ N/2 + O(1), matching the top-interval construction. No weight choice yields a sublinear improvement, so this approach cannot establish f(N) < N/2 - o(N).
Model the interval as a poset ordered by divisibility. The condition 'no element divides two others' means no element has two selected multiples, which is a local constraint on the comparability graph. Use chain/antichain decompositions or a matching argument in the bipartite graph of divisors vs. multiples to derive an upper bound, and identify the extremal structure (likely a union of chains or a threshold set). Formalize the decomposition lemma in Lean.
The poset chain-decomposition 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 gives the bound U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1), which is strictly larger than N for every N in 1..2000 (hence vacuous). Exact computation for N<=30 and randomized search for N<=60 confirm f(N)=ceil(N/2) for N>=4 (f(4)=3), so the true maximum is about N/2, but no chain-decomposition/matching argument in this direction produces a matching upper bound. The only rigorous statement available is the trivial lower bound from the top interval {floor(N/2)+1,...,N}, which is already known and not a new hypothesis.
Write a brute-force or dynamic-programming search to compute the exact maximum for intervals [1,n] and [a,b] for small n, then fit the growth rate and identify the extremal patterns. Use the computed data to conjecture the exact formula or asymptotic constant, and prove the simplest observed lemma (e.g., monotonicity or a recurrence) in Lean. This direction is lower priority because it is exploratory, but it can guide the other two.
The exact-computation-and-pattern-extrapolation direction is exhausted. Exact branch-and-bound (validated by brute force for N<=24 and cross-checked with an independent ILP for N<=60) already 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. The known asymptotic f(N) ~ 0.6735N (DHSW 2020) is consistent with this 2/3 density. A finite search over small N cannot prove the asymptotic constant, and re-running the same bounded computation would repeat a rejected direction. The useful next step is the parallel weighted-divisor upper bound or poset chain-decomposition attack, not more small-N enumeration.
No limit configured for this iteration.