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 54.
93 RECORDS
7 objects · 0 links · 9 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 condition as a 3-uniform hypergraph on [n] with edges {x,y,z} where x|y and x|z. Use the divisibility poset structure: partition [n] into chains (e.g., by odd part), then any set with no x dividing two others has at most one element in each chain? Actually that is false, but we can use chain decompositions to get fractional coverings: assign weights to chains and to pairs (x,{y,z}) to derive an LP dual upper bound. Try to prove a clean bound like |S| <= n/2 + O(sqrt n) or better by constructing a fractional packing of constraints. This is a structural extremal approach, not random sampling.
The poset chain-decomposition and LP-dual upper-bound direction is exhausted. (1) The odd-part chain decomposition gives only U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1), which is > N for all N in 1..20 (e.g. U(20)=21), hence vacuous. (2) The natural LP relaxation of the 3-uniform hypergraph independent-set problem (variables x_i in [0,1], constraints x_x + x_y + x_z <= 2 for every triple x|y, x|z) has optimum exactly N for every N<=40, attained by the all-ones dual solution; so the LP dual cannot beat the trivial bound N. No nontrivial upper bound (e.g. 2N/3 + o(N)) is derivable from this direction alone.
Partition [n] into dyadic blocks (n/2^{k+1}, n/2^k] and residue classes modulo powers of 2. Within each block, divisibility by small factors creates local constraints. Use a greedy/inductive argument: bound the maximum size by summing over blocks, using that an element in a high block can divide at most one element in each lower block, and optimize the allocation. This gives constructive upper bounds via explicit extremal configurations, distinct from the rejected near-n intervals.
The residue-class and dyadic-block decomposition direction is exhausted. Partitioning [N] into dyadic blocks (N/2^{k+1}, N/2^k] and/or residue classes modulo powers of 2, the only constraints on a subset S with no element dividing two distinct others are: (i) each block contributes at most its size, and (ii) an element in a higher block can divide at most one element in each lower block. But (ii) is implied by (i): the number of elements in a lower block is at most the block size, and the total number of elements in all lower blocks is at least the size of any higher block. The LP relaxation over these constraints has optimum N (take all elements), so no nontrivial upper bound follows. This matches the earlier finding that the dyadic-block recursion / divisor-count-profile LP is exhausted.
Use the divisor function to count, for a candidate set S, the number of triples (x,y,z) with x|y, x|z. Apply the second-moment method: if |S| is too large, the expected number of such triples under a suitable weighting exceeds the number of possible x, forcing a forbidden triple. Optimize using known estimates for sum_{x<=n} d(x)^2 and correlations. This is analytic and complements the structural approaches; it avoids the rejected random sampling by using deterministic weights and higher moments.
The second-moment/divisor-sum analytic direction is exhausted as a route to a sharp upper bound on f(N). The condition 'no element divides two distinct others' gives only: (1) for each a in S, the number of multiples of a in S is at most 2, so sum_{a in S} d_S(a) <= 2|S|; (2) Cauchy-Schwarz lower bounds on the number of forbidden triples, which for any weighting w yield (sum w(a)(d_S(a)-1))^2 / (sum w(a)^2 d_S(a)^2) <= number of triples, and the trivial upper bound on triples is sum_{a<=N} d(a)^2 ~ N log^3 N, which is too weak to force |S| <= cN for any c<1; (3) the LP relaxation max sum x_i s.t. 0<=x_i<=1 and sum_{b: a|b} x_b <= 1 for all a, whose dual is a fractional chain/path cover and gives only the trivial |S| <= N. The exact computation for N<=40 confirms f(N)=ceil(N/2) except N=4, but this is finite evidence, not a proof. No new analytic inequality was found that improves on these barriers.
Model the condition as a 3-uniform hypergraph on [n] where edges are triples (a,b,c) with a|b and a|c. Use the Lovász local lemma or entropy compression to show that any subset of size > c n / log n must contain such a triple, by analyzing the local structure of the divisor poset. Prove a quantitative upper bound and formalize the key counting lemma in Lean.
The density/entropy upper-bound direction via random sampling and the divisor graph is exhausted and cannot yield a nontrivial upper bound on f(N). (1) The top-half set T={floor(N/2)+1,...,N} is valid and has size ceil(N/2), so f(N) >= ceil(N/2); any upper bound must be at least this. (2) The forbidden-triple hypergraph has edges (a,b,c) with a|b, a|c, b!=c; the expected number of such 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=1/2, yielding only |S| <= N/2 - N^2/32, which is negative for N>16 and useless. (3) The valid-set family is not hereditary (deleting an element can create a forbidden triple, e.g. {2,4,8} -> {4,8}), so entropy arguments give only log2|S| <= log2 N. (4) The divisor-graph VC-dimension approach cannot separate the top-half set from a random set because the top-half set has the same local divisor structure (each element has at most one multiple in the set).
Build large subsets with no element dividing two others. For example, take all numbers in (n/2, n] (size n/2) or all multiples of a prime p > n/2 (size floor(n/p)). Investigate hybrid constructions (e.g., union of a high interval and a sparse set of small numbers) to push the lower bound beyond n/2, and prove the construction is valid.
The constructive lower-bound direction via multiples of a large prime and near-n intervals is exhausted. (1) The top-half interval {floor(N/2)+1,...,N} is a valid construction of size ceil(N/2), but the known asymptotic f(N) ~ 0.6735N (DHSW 2020) already exceeds ceil(N/2) for large N, so no construction of density 1/2 can be the answer. (2) The large-prime construction is exhausted: for p > N/2 the base layer is {p} (or {p,2p} if p <= N/2), so it has size at most 2, and adding any non-multiple x of p creates a forbidden triple. (3) The layered construction (N/3,N] plus lower elements with exactly one multiple never exceeds ceil(N/2) in any tested case (exact backtracking for N<=60 and shifted intervals [x+1,x+N], x<=20, N<=30), so it cannot provide a lower bound beyond the trivial one. Therefore this direction cannot push the lower bound beyond ceil(N/2), and the known asymptotic f(N) ~ 0.6735N already exceeds that.
Write a branch-and-bound or ILP solver to compute the exact maximum for n up to 50 or 100, and analyze the optimal sets to guess the asymptotic form. Use the computed data to refine conjectures and identify extremal structures, then formalize the verified small-n results in Lean as a benchmark for future bounds.
This direction is exhausted. Exact computation and pattern detection for small n was already completed and cross-validated in earlier iterations: for every N<=200, exact 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) for x<=20, N<=30. No alternative extremal structure or counterexample was found in that range. Re-running the same search would only reproduce known data and would not justify any new hypothesis or Lean lemma beyond what is already established.
No limit configured for this iteration.