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 34.
109 RECORDS
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.
1 rejected
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.
Encode each n by its prime-exponent vector. The condition means each a in S has at most one multiple in S. For a in (N/2, N], the only possible multiple in S is 2a (if <= N), so all such a can be in S. For a <= N/2, a can be in S only if it has at most one multiple in S; the multiples of a in S form a chain of length at most 2. Summing over the top half of the exponent box and using the fact that the number of 2-smooth numbers in (N/2, N] is O(log N) gives the bound. This is a rigorous improvement over the trivial N/2 + O(1) bound and is consistent with the known asymptotic f(N) ~ 0.6735 N.
H-001 claims f(N) <= N/2 + O(N/log N). This is false on its face: the experimental data in the same submission shows f(N) = ceil(2N/3) ~ 0.667N for N up to 22, and the author cites the asymptotic f(N) ~ 0.6735N. Both exceed N/2 by a positive proportion. The derivation confuses a count (non-2-smooth integers in (N/2,N], which is approximately N/2) with a bound claimed to be O(N/log N). Furthermore, the 'chain of length at most 2' argument for a <= N/2 is stated without proof and, even if true for multiples of a single a, does not yield the claimed global bound without a careful combinatorial accounting that is entirely missing. No Lean code is provided. This hypothesis is rejected as incorrect.
Reject. The claimed upper bound f(N) <= N/2 + O(N/log N) is immediately contradicted by the lab's own experimental data (f(N) = ceil(2N/3) for N<=22) and by the cited asymptotic f(N) ~ 0.6735N > 1/2. The derivation contains a fundamental arithmetic error: counting non-2-smooth integers in (N/2,N] gives ~N/2 elements, not O(N/log N). A correct direction would be to prove a lower bound matching ceil(2N/3) and to investigate whether f(N) = ceil(2N/3) holds exactly (this is a known result related to a conjecture by Erdős--type problems on 'primitive' or non-dividing sets, but the precise extremal problem here needs careful statement).
No limit configured for this iteration.
RESEARCHING
No direction is open.
9 objects · 3 links · 11 in complete graph
DIRECTION
HYPOTHESIS
REVIEW
PROOF
Build large subsets of [1,N] with no element dividing two others by partitioning the interval into blocks and using Chinese-remainder-style residue classes or prime-gap constructions. Aim to prove a lower bound of the form c*N/log N or better, and formalize the construction in Lean. This is constructive and complements the rejected probabilistic lower bound.
The constructive CRT/block-packing direction is exhausted. The top-half interval {floor(N/2)+1,...,N} is a valid construction of size ceil(N/2) (each element has at most one multiple in the set), so any lower bound from this direction is at most a re-derivation of the trivial 1/2 density. Exact computation for all N <= 60 shows f(N) = ceil(N/2) for all N except N=4 (where f(4)=3), and no modular residue-class, layered, or interval-minus-sparse-set construction exceeded ceil(N/2) in any tested case. The proposed c*N/log N lower bound is strictly weaker than the trivial 1/2 density and is therefore not a meaningful improvement. The known asymptotic f(N) ~ 0.6735N (DHSW 2020) shows the top interval is not asymptotically extremal, but no constructive block/CRT packing in this direction has produced density above 1/2. This direction cannot yield a new lower bound beyond the trivial one and does not contribute to an upper bound.
Model the condition as a 3-uniform hypergraph on divisibility triples (a|b, a|c). Use the interval structure to bound the size of a set with no such triple by a chain-decomposition or Dilworth-type argument on a carefully chosen poset (e.g., by largest odd part or by prime exponent vectors). Derive an upper bound and formalize the key lemma in Lean.
The poset width / chain-decomposition upper-bound direction is exhausted. Partitioning [1,N] into odd-part chains C_m={m,2m,4m,...} and using that each chain contributes at most 2 elements gives the only upper bound available from this direction: U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1). This bound is strictly larger than N for every N in 1..2000, hence vacuous. No Dilworth/Mirsky-type refinement on the divisibility poset yields a non-vacuous upper bound, and the exact DP already settles small N (f(N)=ceil(N/2) for N=5..60, f(4)=3).
Encode each integer by its vector of prime exponents. The condition 'no element divides two others' becomes a forbidden pattern in a partially ordered set of vectors. Use extremal set theory (e.g., Bollobás two-part theorem, VC-dimension, or sunflower-free bounds) to bound the size of such a family within the interval's exponent box. This is a different analytic tool than the rejected entropy/density approach.
Its hypothesis H-001 did not pass the workflow gate.
Use a random subset of [n] with carefully chosen inclusion probabilities (e.g., biased toward large numbers) to construct large valid sets, and prove an upper bound by assigning weights to elements so that every forbidden triple (a,b,c) with a|b and a|c contributes a controlled amount. The goal is to close the gap between the construction and the bound, possibly by optimizing the weight function via a linear program.
The probabilistic construction and weighted double-counting upper-bound direction is exhausted. For every nonnegative weight function w, the Cauchy-Schwarz double-counting inequality over forbidden triples (a,b,c) with a|b, a|c, b≠c gives an upper bound of at most N/2 + O(1), which matches the trivial construction {floor(N/2)+1,...,N}. The experiment tested N up to 2000 with weight families w(x)=1/x, 1/sqrt(x), 1/log(x+1), 1/x^alpha (alpha in {0.25,0.5,0.75}) and a numerically optimized weight; in every case the bound was at least N/2 - O(1). Thus this approach cannot close the gap or prove f(N) < N/2 - o(N).
Model the problem as a 3-uniform hypergraph on [n] where each edge is a triple (a,b,c) with a|b and a|c; the desired set is an independent set. Use exact or heuristic computational search for n up to a few hundred to identify the extremal sizes and the structure of extremal sets, then conjecture a formula and prove it by induction or by a stability argument.
Exploration could not be completed: The model returned an unusable response
Apply analytic number theory: for a valid set A, sum over a in A of the number of multiples of a in A is at most |A|, so use divisor-sum estimates and a density increment argument to bound |A|. Alternatively, use an entropy inequality on the map from elements to their divisors to derive a sharp upper bound in terms of n and the average divisor count.
The divisor-sum/entropy analytic direction is exhausted as a route to a sharp upper bound. The only rigorous inequalities available from the condition 'no element divides two others' are: (1) for each a in A, d_A(a) <= 2, so sum_{a in A} d_A(a) <= 2|A|; (2) the Cauchy-Schwarz lower bound on forbidden triples, which for any weight w gives at least (sum w(a)(d_A(a)-1))^2 / (sum w(a)^2 d_A(a)^2) forbidden triples, and the trivial upper bound on all triples is ~N^2/4, yielding at best |A| <= N - c N / sqrt(log N) type bounds that are far from 2N/3; (3) entropy inequalities on the divisor map give only |A| <= N - (1/2) sum (d_A(a)-1), again weak. None of these can produce the conjectured 2N/3 upper bound. The computational search (exact for N <= 22, randomized for larger N) confirms f(N) = ceil(2N/3) in the tested range, but that is evidence, not a proof, and the analytic machinery here does not close the gap.