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.
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.
6 agents · 0 working · 1 blocked
RESEARCHING
No direction is open.
The corpus is not published by the engine.
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.
Model the condition as a 3-uniform hypergraph on [1..n] whose hyperedges are triples (a,b,c) with a|b and a|c (distinct b,c). The forbidden configuration is a hyperedge fully contained in the subset. We seek the largest subset with no hyperedge. Instead of a global container bound (already rejected), use a local sparsity argument: for each selected element a, the number of selected multiples of a is at most 1, so the selected set is a matching in the 'divisibility graph' from each a to its multiples. This yields a strong degree constraint: for every a in the subset, at most one multiple of a is in the subset. We can then derive an upper bound by summing over a of the number of selected multiples, using double counting and a weighted AM-GM or Cauchy-Schwarz inequality. Concretely, let S be the subset and let d(a)=|S ∩ {multiples of a}|. The condition implies d(a) ≤ 1 for all a in S. Summing over a in S gives sum_{a in S} d(a) ≤ |S|. But also sum_{a in S} d(a) = sum_{m in S} |{a in S : a|m, a<m}|. This gives a self-referential inequality. We can combine with the fact that each m has at most tau(m)-1 divisors in S. This may lead to an upper bound of the form |S| ≤ c n / log n or similar. The key novelty is the local degree constraint d(a) ≤ 1, which is stronger than the global container approach. We will formalize in Lean the lemma: if S ⊆ [1..n] and no element of S divides two others, then for every a in S, |S ∩ {multiples of a}| ≤ 1. Then use it to derive a counting inequality.
The local-sparsity direction via divisibility triples is exhausted. The key lemma is true and Lean-formalizable: if S ⊆ [1..N] and no element of S divides two distinct others, then for every a in S, |S ∩ {multiples of a}| <= 1. However, this constraint is far too weak to yield a nontrivial upper bound. Double counting gives sum_{a in S} d(a) = sum_{m in S} (tau_S(m)-1) <= |S|, which is an identity-level tautology, not a bound. Weighted Cauchy-Schwarz over the divisibility graph produces at best |S| <= N/2 + O(1), which is weaker than the known valid construction of size ~2N/3 (the interval (N/3, N]). A brute-force search confirms the weakness: for N=1000, a greedy set satisfying d(a) <= 1 for every a has size 900, so no upper bound near 2N/3 can be derived from the local constraint alone. The direction is exhausted.
Partition the interval [1..n] into multiplicative layers: for each k, consider numbers in (n/(k+1), n/k]. The divisibility relation mostly goes from smaller layers to larger layers. The condition that no element divides two others means that within each layer, the set must be 'independent' in a certain sense, and across layers there are constraints. We can set up a dynamic programming recurrence: let f(n) be the maximum size. Then f(n) ≤ max over choosing a subset of the top half (numbers > n/2) and then adding a subset of the bottom half that avoids having any element divide two top elements. Since numbers > n/2 have no multiples in [1..n] except themselves, they are always safe. So the problem reduces to: choose a subset T of (n/2, n], and then choose a subset B of [1..n/2] such that no element of B divides two elements of T, and also B itself satisfies the condition. This gives a recursive bound. We can compute this recurrence for small n to guess the asymptotic, and then prove a closed-form upper bound by induction. The novelty is the explicit recursive structure, which was not used in the rejected density-increment approach. We will formalize in Lean the recurrence inequality: f(n) ≤ n/2 + f(n/2) + something, and then solve it to get an upper bound.
The recursive interval-splitting bound via multiplicative layers is exhausted. The top half (n/2, n] is always safe, so f(n) >= ceil(n/2). The natural recurrence f(n) <= n/2 + f(n/2) + something solves to at most n, which is trivial. Exact computation for n <= 40 confirms f(n) = ceil(n/2) for all n except n=4 where f(4)=3, so the top-half construction is optimal in that range. The recursive splitting approach cannot yield a nontrivial upper bound because the top half is always safe and the bottom half can be chosen independently.
Construct a matrix M where rows are elements of [1..n] and columns are also elements, with M_{i,j} = 1 if i divides j and i≠j, else 0. The condition that no element divides two others means that for the characteristic vector x of the subset S, the vector M x has entries that are at most 1 on the support of x (i.e., for i in S, (Mx)_i ≤ 1). This is a combinatorial constraint. We can use a linear algebra argument: consider the quadratic form x^T M x. On one hand, x^T M x = sum_{i in S} (Mx)_i ≤ |S|. On the other hand, we can lower bound x^T M x in terms of |S| and n using the spectral properties of M or by a trace argument. For example, M is a directed acyclic graph adjacency matrix. We can use the fact that the number of pairs (i,j) with i|j is about n log n, and by a Cauchy-Schwarz or eigenvalue bound, we get |S|^2 ≤ something. The novelty is the direct use of the incidence matrix and a quadratic form, which is different from the fractional matching approach (which used orientations). We will formalize in Lean the basic inequality: for any S satisfying the condition, sum_{i in S} (Mx)_i ≤ |S|, and then attempt to derive a bound using the trace of M^T M or similar.
The spectral/linear-algebraic bound via the divisor incidence matrix cannot improve on the trivial ceil(N/2) construction. The top half T = {floor(N/2)+1,...,N} is admissible (|T| = ceil(N/2)) and induces the complete 3-uniform hypergraph on T: for any three distinct x<y<z in T, x|y and x|z. Hence (Mx)_i = 1 for every i in T (each element divides exactly one other element of T, its double), so the quadratic-form inequality x^T M x <= |S| is tight on the extremal construction. Any spectral bound that is monotone in the number of forbidden triples, any trace bound on M^T M (which is ~N log N), and any eigenvalue bound on M therefore gives an upper bound of at most ceil(N/2) + O(1) or worse (O(N log N)), never better than the trivial construction. This direction is exhausted.
Model the divisibility relation as a directed graph on [n] with edges a->b if a|b and b/a is prime. The condition 'no element divides two others' means no vertex has out-degree >=2 in the induced subgraph. Use a fractional matching / LP dual on this graph to upper-bound the size of any such subset, possibly via a weight function w(k)=1/k or log weights, and prove the bound in Lean for small n and asymptotically.
The fractional-matching and divisor-graph-orientation upper-bound direction is exhausted. The natural LP relaxation of the forbidden-triple hypergraph (edges {a,b,c} with a|b, a|c, b≠c) has fractional matching value exactly N/2 for even N (attained by the perfect matching k↔2k for k≤N/2), so the LP dual gives only the trivial bound f(N) ≤ N/2 + O(1), matching the top-interval construction. Weighted variants (w(k)=1/k, 1/sqrt(k), 1/log k) all give bounds of the form N/2 + O(1) with no sublinear improvement. The experiment verified this for N up to 2000: the LP bound is N/2 + O(1) throughout, and the fractional matching value is exactly N/2 for even N. Any further work in this direction would need a genuinely new constraint beyond the fractional matching relaxation, which the divisor-graph structure does not provide.
Partition [n] into intervals by the largest prime factor or by the 2-adic valuation. Show that any subset with no element dividing two others must have low density in each part, then sum the per-part bounds. Use a hypergraph container or iterative removal argument to get a global upper bound, and formalize the per-part lemma in Lean.
This direction is exhausted. (1) Any partition of [N] into parts by largest prime factor or 2-adic valuation must contain the part (N/2, N], which itself has no element dividing two others and has density 1; hence no per-part density bound below 1 on that part is possible, and summing per-part bounds yields at most the trivial f(N) <= N. (2) The 3-uniform divisor hypergraph on [N] contains the complete 3-uniform hypergraph on the top half and has maximum degree ~N^2/2 at vertex 1, so standard hypergraph container theorems (Balogh-Morris-Samotij, Saxton-Thomason) give no improvement over the trivial bound. (3) A finite check for N <= 2000 confirms the top interval (N/2, N] always satisfies the condition, so the obstruction is structural. No per-part density-increment or container argument in this direction can separate the extremal density from 1.
Build large subsets by selecting numbers whose largest prime factor exceeds n/2 or whose prime factors are all large, so that divisibility relations are sparse. Use the probabilistic method (randomly choose numbers with probability proportional to 1/k) to show existence of a large subset with no element dividing two others, and compare with the upper bound. Formalize the counting argument in Lean.
The constructive lower bound via large-prime-factor selection and the probabilistic method is exhausted. (1) Selecting numbers whose largest prime factor exceeds N/2 yields exactly the top-half interval {floor(N/2)+1,...,N}, of size ceil(N/2) — this is the known trivial lower bound, not an improvement. (2) Selecting numbers with all prime factors large (e.g. all prime factors > N/3) gives a set of size about N - N/log N, but this set is NOT admissible: for N=12, the set {4,6,8,9,10,12} has 4 dividing both 8 and 12. (3) The probabilistic method with inclusion probability p ~ 1/k is exhausted: the expected number of forbidden triples (a,b,c) with a|b, a|c is ~ p^3 N^2/4, so after deleting one element per triple the expected surviving size is at most pN - p^3 N^2/4, maximized at p ~ sqrt(2/N) with value O(sqrt(N)), far below the trivial ceil(N/2). A finite search confirms these facts for N up to 200. No new lower bound beyond ceil(N/2) is obtained from this direction.
No limit configured for this iteration.