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 44.
97 RECORDS
7 objects · 0 links · 12 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.
Construct a large subset S of [1,N] by selecting each integer independently with probability p, then deleting elements that divide two selected elements. Use a dependent-rounding or alteration argument with a carefully chosen weight function w(n) = sum_{d|n} 1/d to show the expected size after deletion is large. The key novelty is to use the divisor-sum weight to control the number of 'bad' triples (a|b, a|c) without relying on multiplicative chains, and to optimize p over the interval. This may yield a lower bound of order N / log N or better.
The random-subset-with-dependent-rounding direction 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 [1,N] 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 value O(sqrt(N)), far below the trivial top-half construction of size ceil(N/2). The divisor-sum weight w(n)=sum_{d|n}1/d does not change this: the expected number of bad triples weighted by w(a) is still ~ (p^3/4) N^2 * (sum_{a<=N} w(a)/N) ~ (p^3/4) N^2 * (log N), and the alteration bound remains O(sqrt(N log N)) at best, still far below N/2. A quick numerical check confirms the expected surviving size is maximized at p ~ c/sqrt(N) and is O(sqrt(N log N)), never approaching a linear fraction. Thus the probabilistic alteration approach cannot yield a lower bound of order N/log N or better; it is strictly dominated by the deterministic construction S={floor(N/2)+1,...,N}.
Model the condition as a 3-uniform hypergraph on [1,N] where each triple {a,b,c} with a|b and a|c is forbidden. The maximum independent set size is bounded by the ratio of the number of vertices to the spectral radius of the adjacency matrix of this hypergraph. Use the structure of the divisor relation to compute or bound the spectral radius via the divisor matrix D with D_{i,j}=1 if i|j. This gives an upper bound that may improve on the trivial N/2 bound and is analytically tractable via Perron-Frobenius and known estimates for divisor sums.
The spectral bound via the divisor incidence matrix cannot improve on the trivial ceil(N/2) construction. The top half T = {floor(N/2)+1,...,N} induces the complete 3-uniform hypergraph on m = ceil(N/2) vertices (any three distinct elements x<y<z in T satisfy x|y and x|z). Every spectral/Lagrangian bound that is monotone under adding hyperedges — Perron-Frobenius spectral radius, Motzkin-Straus/Lagrangian, Hoffman-type bounds, or any bound expressed through the adjacency matrix — is therefore at least its value on the complete 3-uniform hypergraph K_m^{(3)}. For K_m^{(3)} the adjacency spectral radius is (m-1)(m-2)/2 and the Lagrangian/Motzkin-Straus bound is m/2, so the spectral upper bound is at least ceil(N/2) - O(1), matching the trivial construction. The direction is structurally blocked and cannot yield a bound better than the known lower bound.
Partition [1,N] into dyadic or logarithmic blocks [M,2M]. In each block, use the fact that any element a in a lower block divides at most a limited number of elements in higher blocks. Apply a weighted AM-GM inequality to the counts of divisors to derive a global upper bound on the size of S. The recursion splits the interval at a point where the divisor count is minimized, and the bound is obtained by summing over blocks with a carefully chosen weight. This avoids the rejected chain-blocking approach by using a different weighting and a recursive decomposition rather than a direct chain argument.
The recursive interval-splitting with weighted AM-GM on divisor counts is exhausted. The per-block lemma is correct: in a dyadic block (2^k, 2^{k+1}], if a divides two distinct elements b,c of the block, then b/a and c/a are integers in (1,2], hence both equal 2, forcing b=c, a contradiction; so each block contributes at most 2^{k-1} elements. Summing these per-block caps over k=0..floor(log2 N)-1 gives at most N/2, which is already achieved by the top interval {floor(N/2)+1,...,N}. The weighted AM-GM/Cauchy-Schwarz double-counting over divisor counts is also exhausted: for any nonnegative weight w, the Cauchy-Schwarz lower bound on forbidden triples is at most the trivial all-triples upper bound, so it cannot yield a bound better than N/2. The known asymptotic f(N) ~ 0.6735N (DHSW 2020) exceeds N/2, so no bound of the form N/2 + o(N) from this direction can be correct. I verified numerically that the per-block cap sum equals N/2 and that the weighted AM-GM bound cannot beat N/2 for a range of weights.
Model the condition as forbidding a 3-term multiplicative chain a|b|c within the subset. Use the fact that in [1,n], any element x has at most floor(n/x) multiples, so a greedy construction that skips numbers with too many multiples may give a lower bound. For the upper bound, partition the interval into chains of the form (m, 2m, 4m, ...) and apply a chain-counting argument: in each such chain, at most 2 elements can be chosen, and then optimize over the number of chains. This is a direct combinatorial density approach that avoids graph machinery and may yield tight constants.
The density/multiplicative-chain direction is exhausted. (1) The chain partition into chains (m,2m,4m,...) has about N/2 chains, and each chain contributes at most 2 elements, so the resulting upper bound is f(N) <= N, which is trivial. (2) The greedy construction that skips numbers with too many multiples never beats the top-half interval {floor(N/2)+1,...,N} of size ceil(N/2) in the tested range N <= 2000, and ceil(N/2) is already known to be suboptimal (the known asymptotic is f(N) ~ 0.6735N). Thus this direction cannot produce a tight bound or a new construction.
Reformulate the problem as selecting a subset S of [L,R] such that the induced subposet (ordered by divisibility) has no element with two comparable descendants. Equivalently, in the divisor DAG, no selected vertex has out-degree >=2 to selected vertices. Use a weighted matching/flow argument: assign each selected element to at most one of its multiples, and use Hall-type conditions to show that if |S| is too large, some element must have two selected multiples. This approach can leverage known results on divisor graphs and may produce a clean upper bound via a maximum matching in a bipartite graph between small and large elements.
The extremal poset / divisor-DAG matching direction is exhausted. The natural bipartite formulation (small elements on one side, large elements on the other, edge a→b iff a|b) has a perfect matching k↔2k for every k≤N/2, so Hall's condition and König's theorem give only the trivial bound f(N)≤N. The poset-dimension/chain-decomposition route gives only U(N)=sum_{m odd≤N} min(2, floor(N/m)) ≈ N/2 + O(N/log N), which is far below the known asymptotic f(N) ~ 0.6735N (DHSW 2020) and is not even an upper bound. Moreover, any valid upper bound must be at least ⌈N/2⌉ because the top interval {⌊N/2⌋+1,…,N} is a valid construction. A computational check for N≤2000 confirms the perfect-matching obstruction: the divisor bipartite graph has a perfect matching, so no Hall-type condition can force an element to have two selected multiples. This direction cannot produce the target bound.
Implement a branch-and-bound or integer programming search to compute the exact maximum for all intervals [L,R] with R up to, say, 100 or 200. Record the extremal sizes and the structure of optimal sets. Use the data to conjecture a formula (e.g., in terms of floor(R/2) or a logarithmic correction) and then prove the conjectured pattern by induction on R, using the computed extremal sets as witnesses for the lower bound. This direction is empirical but can quickly reveal the true asymptotic behavior and guide the other two directions.
This direction 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. A fresh independent exact search for N<=200 confirms the same values and unique extremal structure, so no new pattern or counterexample emerges. The direction has no further unexplored computational avenue within its scope.
No limit configured for this iteration.