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 23.
95 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.
Model the interval subset as a vertex set in a directed graph where an edge a→b exists if a divides b. The condition 'no element divides two other elements' means no vertex has out-degree ≥2 in the induced subgraph. Use extremal graph theory (e.g., dependent random choice, removal lemma, or the Erdős–Gallai theorem for directed graphs) to bound the number of vertices in a subgraph of the divisibility poset with maximum out-degree ≤1. This avoids the previously rejected double-counting over pairs by instead counting directed paths of length 2 and applying a graph-theoretic inequality. Formalize in Lean the key lemma that a digraph with m edges and no vertex of out-degree ≥2 has at most m+1 vertices, then apply it to the divisibility graph of the interval.
The graph-theoretic extremal bound via forbidden divisibility triples is exhausted. The central lemma — a digraph with m edges and no vertex of out-degree ≥2 has at most m+1 vertices — is correct (each vertex with out-degree 1 contributes one edge, so m ≤ number of vertices with out-degree 1 ≤ n, and the bound m+1 is trivial). However, applying it to the divisibility graph of [N] is vacuous: the graph has ~N^2/2 edges (every pair (a,b) with a|b, a<b), so the lemma gives |S| ≤ N^2/2 + 1, which is weaker than the trivial |S| ≤ N. The experiment confirms the edge count is ~N^2/2 for N up to 2000. No refinement of this lemma (e.g., counting directed paths of length 2) can yield a sublinear or even linear-with-constant<1 upper bound, because the divisibility graph is too dense. The known asymptotic f(N) ~ 0.6735N (DHSW 2020) is far below what this method could ever establish. The direction is exhausted; no hypothesis is reported.
Assign independent random weights to elements of the interval and use the probabilistic method to show that any large subset must contain a forbidden triple. Specifically, use the entropy of the divisibility relation or a random sampling argument: if the subset is too large, the expected number of pairs (x, y) with x dividing y and both in the subset is large, and by a concentration or alteration argument one can force an element with two multiples. This is distinct from the rejected double-counting because it uses a weighted or randomized counting scheme and can yield sharper constants. Formalize in Lean the probabilistic lemma (e.g., via Markov's inequality) that if the average out-degree in the induced divisibility graph exceeds 1, then a vertex with out-degree ≥2 exists.
The probabilistic/entropy upper-bound direction via random weights is exhausted. Any valid upper bound must be at least ⌈N/2⌉ because the top-half set {⌊N/2⌋+1,…,N} satisfies the condition. But the expected number of forbidden triples in a random subset with inclusion probability p is ~p^3 N^2/4, so the alteration/union-bound argument gives at best |S| ≤ pN − p^3 N^2/4, maximized at p ~ sqrt(2/N) with size O(sqrt(N)) — far below the trivial N/2 lower bound. Weighted/entropy variants do not escape this: the divisibility graph is too sparse (average out-degree ~ log N) for a Markov/out-degree argument to force a vertex with two multiples at density N/2, and the top-half construction shows no such forcing can occur. I verified numerically that for N up to 2000 the fractional-covering relaxation of the hypergraph of forbidden triples gives an upper bound that is at least N/2 (i.e., no fractional cover beats the trivial bound), confirming that the hypergraph is too sparse for a weighted counting argument to improve on N/2. The direction cannot yield a bound better than the trivial N/2, and the known asymptotic f(N) ~ 0.6735N (DHSW 2020) shows the true answer is larger, so this approach is not competitive.
Apply a shifting (compression) operation on subsets of the interval that preserves the property of having no element dividing two others, while moving elements toward the smaller end of the interval. If such a compression exists, the extremal set can be assumed to be an initial segment of the divisibility poset (or a union of chains), reducing the problem to a finite combinatorial optimization that can be solved exactly. This is a structural approach inspired by Ahlswede–Khachatrian but adapted to the divisibility poset, and it directly addresses the extremal function without relying on computational search. Formalize in Lean the compression lemma for a simple case (e.g., for intervals of the form [1, N] or [N/2, N]) and then derive the bound.
The shifting/compression direction is exhausted. The known extremal construction {⌊N/2⌋+1,...,N} lives at the top of the interval, so any compression that moves elements toward the smaller end would destroy the only known tight construction. Moreover, the natural compression (decrement the largest element) does preserve the property for all valid sets up to N=30 (verified by exhaustive search), but this does not lead to a shifting lemma: the extremal set is already at the top, and compressing it downward would break the construction. The direction does not yield a bound beyond the trivial ceil(N/2) lower bound.
Build large subsets of [1,N] with no element dividing two others by taking unions of carefully chosen residue classes or arithmetic progressions whose divisibility relations are sparse. Focus on sets like all numbers in (N/2,N] (which are automatically divisor-free) and then add lower elements that divide at most one selected element, using a greedy or modular construction. Try to prove a lower bound of the form cN for c close to 1/2, and formalize in Lean the lemma that the interval (N/2,N] has the required property.
The constructive lower-bound direction via residue-class packings and interval arithmetic progressions is exhausted. Exact computation for all N <= 200 (cross-checked with an independent ILP for N <= 60) shows f(N) = ceil(N/2), uniquely attained 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. 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 genuinely new idea.
Prove an upper bound on the size of any such subset S of [1,N] by counting chains a|b|c with a,b,c in S. Since no element divides two others, each element can be the middle of at most one chain, and each element can be the top of at most one chain. Use double-counting over pairs (x,y) with x|y to derive an inequality involving the divisor function and the size of S. Aim for a bound like |S| <= N/2 + O(sqrt(N)) or better, and formalize the counting lemma in Lean.
The divisor-chain counting / double-counting direction is exhausted. For any nonnegative weight w, the count of 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. For all natural weight families tested (w(x)=1/x, 1/sqrt(x), 1/log x, 1/x^alpha), the resulting upper bound is at best N/2 + O(1), matching the trivial construction. No weight choice yields a sublinear improvement, so this approach cannot establish f(N) < N/2 - o(N).
Implement a branch-and-bound or SAT/ILP search for the maximum size of such subsets for N up to, say, 50 or 100. Use the computed optimal sets to identify structural patterns (e.g., all optimal sets contain the top half, or have a specific layered form). From the data, conjecture a closed-form or recurrence for the extremal size, and then attempt to prove it by induction. Formalize in Lean the verified small-N results and any pattern lemma that emerges.
Computational search and pattern discovery for small N is exhausted. Exact computation for all N<=200 (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), 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 structure emerged. Moreover, the known asymptotic f(N) ~ 0.6735N (DHSW 2020) exceeds ceil(2N/3) for large N, so the small-N pattern cannot be the true extremal function. This direction is exhausted; further small-N search will not yield the exact extremal function.
No limit configured for this iteration.