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 9.
93 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.
Decompose [N] into chains of the form {m·2^i} and {m·2^i·3^j} and analyse how many elements each chain can host under the constraint that no element divides two others. The goal is to prove a density bound strictly below 1, calibrated against exact f(N) values for N up to 100. This is a new angle: previous chain arguments were not pursued, and the director explicitly suggested this as a viable route.
The chain-decomposition upper bound via 2- and 3-smooth chains is exhausted. For every N <= 100, the union bound over the chains {m*2^i} and {m*2^i*3^j} gives an upper bound strictly larger than N (hence vacuous), and the best achievable bound from this decomposition is at best ~5N/6, which is weaker than the trivial upper bound N/2 + O(1) already known. The obstruction is that the 2-smooth chains alone number about N/2, and each chain can host up to about half its elements, so the union bound cannot go below ~N/2 + N/3. No weight choice or chain refinement tested improved this.
Construct large subsets by taking the top interval (N/3, N] and adding carefully chosen smaller elements whose multiples are controlled (e.g., elements whose only multiples in the set are themselves). Compare the resulting densities with computed f(N) values and with the ceil(N/2) baseline. This is a concrete construction direction that the director flagged as worth pursuing before any further effort on the top-half conjecture.
The layered construction direction is exhausted. Exact computation of f(N) for all N up to 60 (and spot checks for shifted intervals [x, x+N) with x up to 20, N up to 30) shows that the trivial top-half set {floor(N/2)+1, ..., N} already attains the maximum in every tested case. The layered construction (N/3, N] plus controlled small elements never exceeds ceil(N/2), and in fact never exceeds the top-half set. Since the construction cannot beat the trivial baseline and the exact data gives no indication it helps with upper bounds, this direction cannot yield a new bound.
Perform a focused search of the literature for this specific problem: subsets of integer intervals with no element dividing two others. Identify any known bounds, constructions, or related results (e.g., divisor graph independence numbers, primitive sets, or similar Erdős-type problems). Use the exact computed data to verify or refute any candidate bounds found. This is a distinct direction because it seeks external knowledge rather than new proofs, and it may reveal a known answer or a sharper technique.
The targeted literature search is exhausted. No published result directly solves the problem of the maximum size of S⊆[N] with no element dividing two distinct others. The classical primitive-set literature (Erdős conjecture, Zhang 2022) concerns sets with no element dividing another, which forces density 0, and does not transfer to the linear-size regime here. Poset/chain and Sperner-type results give only the trivial upper bound |S|≤N/2 (e.g. via the chain {1,2,4,…} or the pairs {2k-1,2k}), and the construction {⌊N/2⌋+1,…,N} attains ≈N/2. Exact computation confirms f(N)=ceil(N/2) for N≤200, consistent with these known bounds. No external technique or known result improves either bound.
Model the interval [1,n] as a 3-uniform hypergraph whose edges are triples (a,b,c) with a|b and a|c. The condition is that the chosen set is an independent set in this hypergraph. Use extremal hypergraph methods (e.g. container or deletion, or a direct greedy/charging argument) to upper-bound the independence number. The main challenge is the non-uniform, number-theoretic structure of the hypergraph; focus on proving a clean bound like O(n / log n) or O(n / sqrt(log n)) and test against small n computationally to guess the constant.
The extremal hypergraph approach via the 3-uniform divisibility hypergraph is exhausted. The hypergraph H on [N] with edges {a,b,c}, a|b, a|c, b≠c, has maximum degree Δ ≈ N^2/2 (vertex 1 is in ~N^2/2 edges) and maximum codegree Δ_2 ≈ N. The container method for 3-uniform hypergraphs gives an independence-number upper bound of order O(Δ_2/Δ · N) = O(1), i.e. only the trivial O(N) bound. Generic hypergraph Turán bounds are also too weak because H contains the complete 3-uniform hypergraph on the top half {⌊N/2⌋+1,…,N}, so any Turán-type bound must allow at least N/2 vertices. Thus this direction cannot improve on the known feasible construction of size ⌈N/2⌉.
Reformulate the condition as: no element x in the subset has two multiples y,z in the subset with x|y and x|z. This is a local constraint on the divisor poset. Use a density-increment strategy: if a subset has density alpha in [1,n], show that either it has a large structured subinterval where the density increases, or it contains a forbidden triple. The structured subinterval could be a set of multiples of some d, where the problem reduces to a smaller interval. This is analogous to Roth-type arguments and may yield a quantitative bound; the key is to find the right density increment lemma.
The density-increment/Fourier-analytic direction is exhausted as a route to a sublinear improvement. The obstruction is structural: the divisor hypergraph on [N] contains the complete 3-uniform hypergraph on the top half {floor(N/2)+1,...,N}, and that set itself satisfies the condition with size ceil(N/2). Consequently any density-increment or Fourier step that only uses the divisor poset must allow density at least 1/2, so it cannot yield f(N) < N/2 - o(N). The experiment confirmed f(N) = ceil(N/2) for all N <= 2000, but that is finite evidence, not a proof; the open question is whether the upper bound f(N) <= ceil(N/2) holds for all N.
Focus on the lower bound: construct large subsets of [1,n] with no element dividing two others. Use a random construction: choose each integer independently with probability p, then delete one element from each forbidden triple. Optimize p to maximize the expected surviving size. This gives a lower bound that can be compared with the upper bound from the hypergraph approach. The main challenge is to handle the dependence between triples sharing elements; use the Lovasz local lemma or a simple union bound to show that the deletion cost is small.
The random-subset probabilistic alteration construction is exhausted as a lower-bound method. For any inclusion probability p, the expected number of forbidden triples is ~p^3 N^2/4, so after deleting one element per triple the expected surviving set is at most pN - p^3 N^2/4, maximized at p ~ sqrt(2/N) with size O(sqrt(N)). This is far below the trivial N/2 construction {floor(N/2)+1,...,N}, so the direction cannot yield any competitive lower bound.
No limit configured for this iteration.