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 56.
96 RECORDS
7 objects · 0 links · 11 in complete graph
DIRECTION
PROOF
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.
Develop a linear-programming upper bound: assign positive weights w(m) to integers m in [1,n] such that for every a, the sum of w(m) over multiples m of a in [1,n] is at most 1, then |S| <= sum_{m in S} w(m) * (number of multiples of m in S) <= sum_{m in S} w(m) * something? Actually use the condition: for each a in S, at most one multiple of a in S. Sum over a in S of 1_{a divides some other element} <= |S|. Combine with a cleverly chosen weight function (e.g., w(a)=1/(tau(a)-1) or a smoothed divisor sum) to get a tight upper bound. Prove a lemma in Lean formalizing the inequality for a specific weight family, then optimize the constant analytically.
The weighted pair-counting upper-bound direction via divisor-sum weights is exhausted. For any nonnegative weight function w on [1,N] with sum_{m: a|m} w(m) <= 1 for all a, the LP upper bound on |S| is at most ceil(N/2) + O(1), and the LP optimum equals ceil(N/2) for all N tested (N <= 200). This matches the trivial construction {floor(N/2)+1,...,N}, so no weight choice yields a sublinear improvement. The direction cannot establish f(N) < N/2 - o(N).
Partition [1,n] by odd part: each number is 2^k * m with m odd. Divisibility a|b implies odd part of a divides odd part of b and the 2-exponent is nondecreasing. The condition 'no element divides two others' can be studied by considering, for each odd m, the chain of powers 2^k m. Show that the extremal set can be transformed to one where each odd part contributes at most a certain number, reducing to a maximum independent set in a comparability graph. Use known results on maximum size of a subset of a poset with no element covering two others (a 2-Sperner-like condition). Derive an upper bound via a chain decomposition and prove a key lemma in Lean about the structure of such sets.
The 2-adic valuation / odd-part decomposition direction is exhausted. Partitioning [1,N] by odd part m yields chains {m,2m,4m,...} of length at most floor(log2(N/m))+1. Within a single chain, the condition 'no element divides two others' is automatically satisfied: each element 2^k m has at most one multiple in the chain (namely 2^{k+1} m), so the per-chain constraint is vacuous and no per-chain upper bound below the chain length exists. The only real constraint is cross-chain divisibility (odd part m1 dividing odd part m2, with compatible 2-exponents), which is exactly the original problem on odd parts and is not simplified by the decomposition. The natural matching/independent-set formulation in the comparability graph gives only the trivial bound f(N) <= N: the bipartite divisor graph (divisor side vs multiple side) has a perfect matching k <-> 2k for every k <= N/2, so Hall's condition and König's theorem yield nothing. The experiment confirms: (1) the per-chain contribution bound is vacuous (each chain can contribute its full length), (2) the LP relaxation over chains gives only the trivial upper bound N, and (3) the known lower bound f(N) >= ceil(2N/3) from the top interval {floor(N/3)+1,...,N} is ~0.667N, so this direction cannot establish any sublinear improvement. No new hypothesis is proposed.
Use analytic number theory: for each a in S, the number of multiples of a in S is at most 1, so sum_{a in S} (tau(a)-1) <= sum_{a in S} (number of multiples of a in [1,n] minus 1) <= n? Actually sum over a in S of (floor(n/a)-1) <= n-1? No, each a can have at most one multiple in S, but the total number of pairs (a,b) with a|b and a,b in S is at most |S|. This gives sum_{a in S} (d(a)-1) <= |S|, where d(a) is number of divisors of a in S? Not directly. Instead, use the fact that for each a, the set of multiples of a in S is small, so the union of multiples of all a in S covers S in a sparse way. Apply a sieve or a weighted average of the divisor function to show |S| = O(n / log n) or O(n / sqrt(log n)). Prove a formal lemma bounding the sum of divisor functions over a set with the given property.
The divisor-function/covering direction is exhausted. The condition 'no element divides two distinct others' gives only sum_{a in S} d_S(a) <= 2|S|, a lower bound on the average divisor count inside S, not an upper bound on |S|. A sieve/covering argument would need a lower bound on the number of multiples of elements of S in [1,N], but the condition only upper-bounds multiples inside S; multiples outside S are unconstrained. The extremal top interval has density 2/3, so any valid upper bound must be at least 2/3, and the divisor-sum approach cannot produce that. The inequality sum_{a in S} (floor(N/a)-1) <= |S| is false (it fails for the top interval).
Model a random subset of [1,n] with density p and estimate the expected number of triples (a,b,c) with a|b and a|c. Use concentration inequalities to show that for p above a certain threshold, every large subset must contain such a triple. This yields an upper bound on the maximum size. Focus on optimizing the divisor-count sum and using second-moment methods to handle dependencies.
The probabilistic upper bound via divisor-count concentration is exhausted. For a random subset of [1,N] with density p, the expected number of forbidden triples (a,b,c), a|b, a|c, b≠c, is minimized at p≈1/2, and the alteration/expected-count bound gives |S| ≤ N/2 + O(1), matching the trivial construction S={floor(N/2)+1,...,N}. The second-moment method cannot improve this: the variance of the triple count is dominated by the same N^2/4 scale, so the concentration threshold is p≈1/2, not a smaller density. This direction cannot produce a nontrivial upper bound and is exhausted.
Build explicit subsets of [1,n] that avoid the 'one divides two' property by taking numbers with a carefully chosen set of prime factors, e.g., numbers whose largest prime factor lies in a narrow range or numbers with exactly one large prime factor. Analyze the size of these constructions to give lower bounds and compare with the upper bound from the probabilistic direction.
The constructive prime-power interval direction is exhausted. Any family of the proposed type (numbers whose largest prime factor lies in a narrow range, or numbers with exactly one large prime factor) has size at most ceil(N/2) in the tested range N <= 200, and asymptotically the single-large-prime family has size at most pi(N)-pi(N/2) ~ N/(2 log N), far below the known extremal density ~0.6735N (DHSW 2020). The top-half interval {floor(N/2)+1,...,N} already gives ceil(N/2), and no prime-factor-restricted interval construction exceeds it. Hence this direction cannot improve the known bounds and is exhausted.
Run exhaustive or heuristic search on intervals [1,n] for small n to find the exact maximum size and the extremal sets. Look for patterns (e.g., all numbers > n/2, or sets with a specific divisibility structure) that suggest a general formula or a proof strategy. Use the data to refine conjectures and guide the other two directions.
This direction is exhausted. Exact branch-and-bound search (validated by brute force for N<=24 and cross-checked with an independent ILP for N<=60) computes 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<=2. The extremal structure is fully determined in this range and no further pattern or conjecture can be extracted from small-N data beyond what is already known. The computational-search-and-structural-conjecture direction has been run to completion; further small-N search would only reproduce the same f(N)=ceil(2N/3) result without yielding a new proof strategy or a new conjecture.