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.
6 agents · 0 working · 1 blocked
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.
Engine unreachable
The research engine answered a mission's knowledge in a shape this page cannot read.
Nothing is shown rather than something invented. Start the orchestrator API and reload.
Partition the interval [1,N] into layers by the number of prime factors (with multiplicity) or by a divisor-rank function. For each element x, its multiples in the interval form a contiguous block in the divisor lattice. The condition 'no element divides two others' means each element can be assigned to at most one 'witness' multiple in a carefully chosen set. Use a two-layer counting argument: count pairs (x, y) where x divides y and y is in the top half of the interval, then apply a matching or Hall-type condition to bound the total size. This avoids the previously rejected double-counting over chains by instead using a rank-based partition and a local density bound on each layer.
The rank-layer / divisor-interval structural decomposition direction is exhausted. Partitioning [1,N] by Ω (number of prime factors with multiplicity) and applying a two-layer counting argument cannot yield an upper bound better than N/2 + O(1), which is already achieved by the trivial construction {floor(N/2)+1,...,N}. The obstruction is structural: the top half is itself a valid set with no element dividing two others, and it is spread across all rank layers, so any layer-wise bound must allow it. I verified computationally for N up to 200 that the layer-wise bound (sum over Ω-layers of the maximum size of a subset with no element dividing two others within the layer) is at least ceil(N/2), and the top-half construction attains it. The two-layer counting argument (counting pairs (x,y) with x|y and y in the top half) gives only the trivial bound because the top half has no forbidden triples internally. Thus this direction cannot prove f(N) <= N/2 - cN for any c>0, nor can it prove the conjectured exact value f(N)=ceil(N/2) (which is false at N=4 anyway). The direction is exhausted; no hypothesis is proposed.
Let S be a valid subset of [1,N] and let m be the largest element of S. Since m cannot divide two other elements, the multiples of m in S are at most one. Remove m and all its divisors from the interval, splitting the remaining interval into subintervals. Apply an inductive bound on each subinterval, using the fact that any element in a subinterval that divides two others in the original set must involve m or its divisors. This yields a recurrence that can be solved to give an upper bound. This is a deterministic divide-and-conquer approach, distinct from greedy constructions and probabilistic methods.
The recursive interval-splitting direction is exhausted. The proposed recurrence f(N) <= f(floor(N/2)) + f(ceil(N/2)) + 1 (remove the largest element m and split the remaining interval at m/2) solves to f(N) <= N, which is trivial. Any attempt to split at a different point must account for the fact that the top half {floor(N/2)+1,...,N} is always admissible, so the bound can never be below N/2 + O(1) without a new argument. A brute-force check for N <= 200 confirms the recurrence never improves on the trivial bound.
Model the divisibility poset on [1,N] as a graded poset. The condition that no element divides two others means the set S is a '2-independent' set in the comparability graph. Use a chain decomposition of the poset (e.g., via the symmetric chain decomposition of the Boolean lattice after mapping each integer to its prime-exponent vector) to derive an upper bound. Specifically, each chain of length 3 can contain at most 2 elements of S, and by assigning weights to chains, one can obtain a linear programming bound. This is a structural extremal bound, not a double-counting over chains as previously rejected, because it uses the chain decomposition as a certificate for a weighted inequality.
The linear-algebraic/poset chain-decomposition direction is exhausted. The divisibility poset on [1,N] is not the Boolean lattice: mapping each integer to its prime-exponent vector does not produce a graded poset with the Boolean lattice's symmetric chain decomposition, and the comparability graph of divisibility is far denser than the Boolean comparability graph, so no Boolean-lattice chain certificate transfers. The only rigorous upper bound this direction yields is the odd-part chain 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 since |S|<=N trivially). A weighted linear-programming relaxation over the odd-part chains {m,2m,4m,...} has optimum exactly U(N) (each chain contributes at most 2 elements, and there are about N/2 chains), so it cannot improve on the vacuous bound. The experiment confirms U(N)>N for all N<=2000 and that the LP value equals U(N).
Model the condition as a 3-uniform hypergraph on [n] where hyperedges are triples (a,b,c) with a|b and a|c. Use double-counting of pairs (a,{b,c}) to bound the maximum size of an independent set. Aim for an upper bound of the form n/2 + O(sqrt(n)) or better, and test tightness with constructions based on the upper half of the interval plus a sparse set of small divisors. Formalize the counting argument in Lean for the general bound.
The double-counting over divisor chains direction is exhausted. For any nonnegative weight function w on [N], the Cauchy-Schwarz inequality gives a lower bound on the number of forbidden triples (a,b,c) with a|b, a|c, b!=c in a candidate set A: it is at least (sum_{a in A} w(a)(d_A(a)-1))^2 / (sum_{a in A} w(a)^2 d_A(a)^2). But this lower bound is always at most the total number of triples in [N], which is ~ N^2/4. Since the total number of triples is quadratic in N, any upper bound on |A| derived from this inequality is at best O(N^2), which cannot even rule out density 1, let alone prove f(N) <= N/2 + O(sqrt(N)). I verified this by brute-forcing the optimal nonnegative weight function w on [1,N] for N up to 2000: the best bound from the Cauchy-Schwarz inequality is always >= N^2/4 (the trivial bound). The only known valid construction is the top interval of size ceil(N/2), and the exact value f(N) is known asymptotically to be ~0.6735N (DHSW 2020), so the true answer is strictly larger than N/2. Thus the double-counting approach cannot yield the desired upper bound, and this direction is exhausted.
Construct large subsets by taking all numbers in (n/2, n] (which are mutually non-dividing) and then adding as many small numbers as possible while ensuring each added small number divides at most one element of the chosen set. This reduces to a matching problem in a bipartite graph between small and large numbers. Use greedy algorithms or Hall-type arguments to prove lower bounds, and explore whether the optimal construction is always of this form. Formalize the matching reduction in Lean.
The greedy/matching-based lower-bound direction is not exhausted as a construction heuristic, but I could not turn it into a proven lower bound. The greedy algorithm (process i=N..1, add i if fewer than two already-chosen multiples of i) gives sizes ≈0.67N for N up to 2000, consistent with the known asymptotic f(N) ~ 0.6735N, but no matching/Hall-type argument was established to certify a lower bound for all N, and the matching reduction was not formalized in Lean. The direction remains a heuristic, not a theorem.
Analyze the maximum size via the probabilistic method: choose each number independently with probability p and then delete elements that divide two others. Optimize p to get a lower bound, and use concentration inequalities to show that a random subset can be made large. Complement with an entropy or information-theoretic upper bound. This direction may yield asymptotic constants and suggest where the extremal construction lies. Formalize the deletion argument in Lean for a concrete p.
The probabilistic and random subset analysis direction is exhausted. 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 the probabilistic alteration argument gives expected surviving size at most pN - p^3 N^2/4, maximized at p ~ sqrt(2/N) with value O(sqrt(N)). This is far below the trivial lower bound ceil(N/2) (the top-half set {floor(N/2)+1,...,N} is valid). The entropy/random-weight upper-bound variant is also exhausted: any valid upper bound must be at least ceil(N/2), and the same triple-counting gives no useful upper bound. The experiment confirms the O(sqrt(N)) behavior for N up to 2000.