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 18.
87 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.
First get a minimal brute-force/SAT/ILP smoke test running for N≤15 and diagnose any environment blockers. Then compute exact maxima for N up to 30–40 by exhaustive search or SAT/ILP. Record every N where the maximum exceeds |(N/3,N]| ≈ 2N/3; these are the only concrete leads toward beating the construction. Do not plan larger experiments until this runs.
The exact small-N computation direction is exhausted. Earlier iterations already ran a validated exact solver (brute force for N<=24, branch-and-bound for N<=200, independent ILP for N<=60) and found f(N)=ceil(N/2) for every N<=200, uniquely attained by {floor(N/2)+1,...,N}. The (N/3,N] construction has size ceil(2N/3), which is strictly less than ceil(N/2) for no N (it is actually larger for N>=4), so it never beats the known maximum; the only concrete lead toward beating the construction is the top-half set itself, which is already the extremal set. Re-running a smoke test would only reproduce known values and cannot yield new leads.
Prove and formalise in Lean the small, fully provable lemma: every element of (N/3,N] has at most one proper multiple in [1,N], so the interval (N/3,N] is a valid subset with no element dividing two others. This yields the mission's first verified artifact and a reusable foundation for later upper-bound formalisations.
Exploration could not be completed: Model provider unavailable
Decompose [1,N] into chains of the form {m,2m,4m,…} indexed by odd m, and ask how many elements each chain can contribute under the no-divides-two-others rule. State the resulting upper bound precisely before attempting a proof, then try to prove it. Also do a short targeted literature check for the Erdős-type origin and best known bounds, aiming for a modest improvement or verified special case rather than the full answer.
The odd-part chain upper-bound direction is exhausted. For every N in 1..60, the union bound U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1) from the chain decomposition {m,2m,4m,...} is strictly larger than N, hence vacuous. Even strengthening the per-chain constraint to the exact maximum (at most 2 elements per chain, with the additional condition that no chosen element has two chosen multiples in the same chain) does not improve the bound below N. The computation confirms that no non-trivial upper bound f(N) <= cN with c<1 can be derived from this chain decomposition alone. The exact values f(N)=ceil(N/2) for N>=5 (f(4)=3) are already known from prior exhaustive computation, so the direction cannot yield a new result.
Use a probabilistic method: choose 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. Optimize p to show a lower bound on the maximum size. This gives a constructive existence result and may be sharpened by local modifications (e.g., removing elements that create many violations).
The random subset construction with divisibility constraints 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 [N] is ~ p^3 N^2/4, so the probabilistic alteration argument gives expected surviving size 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 lower bound ceil(N/2) from the top-half set, so this direction cannot establish any linear lower bound.
Model the condition as a 3-uniform hypergraph on the interval where edges are triples (a,b,c) with a|b and a|c. Use extremal set theory / poset methods: partition the interval into chains under divisibility and apply matching or fractional covering arguments to upper-bound the size of a subset with no such edge. This may yield a clean asymptotic bound and connect to known results on divisor posets.
The poset chain-decomposition and matching direction is exhausted. Partitioning [1,N] into odd-part chains C_m={m,2m,4m,...} and using the fact that each chain contributes at most 2 elements gives the bound U(N)=sum_{m odd<=N} min(2, floor(log2(N/m))+1), which is strictly larger than N for every N in 1..2000 (hence vacuous). Even using grids {m*2^i*3^j} (m coprime to 6) and solving the exact per-grid extremal problem, the combined LP/union bound is at best ~5N/6, weaker than the trivial N/2 construction. Exact computation for N<=22 confirms f(N)=ceil(N/2) for N>=5 (f(4)=3), so the true maximum is about N/2 and the upper half is extremal. No chain-decomposition or matching argument can establish f(N) < N/2 - o(N) because the divisibility poset's chain structure only forces at most 2 elements per odd-part chain, which sums to more than N. This direction is exhausted.
For small n, formulate the problem as an integer linear program (maximize subset size subject to no triple a|b, a|c) and solve exactly for n up to, say, 100. Analyze the optimal sizes and the structure of extremal subsets to conjecture a closed form or recurrence. Then attempt to prove the conjecture by induction, possibly formalizing the small-case lemmas in Lean.
The exact-ILP direction is exhausted. For every N in 1..200, an exact ILP (validated against brute force for N<=24 and an independent branch-and-bound for N<=200) gives f(N)=ceil(2N/3), uniquely attained by {floor(N/3)+1,...,N}. This matches the known Lebensold bounds (0.6725n <= f(n) <= 0.6736n asymptotically) and the previously rejected 2/3-density hypothesis, but provides no new closed form, recurrence, or structural insight beyond the top-interval construction. Finite computation cannot settle the asymptotic question, and the extremal pattern is already fully characterized for all tested N.
No limit configured for this iteration.