/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilNumber of different products of subsets of ${1, 2, \dots, n}$
The number of distinct products (including the empty product 1) of any subset of ${1, 2, \dots, n}$.
References:
[Li26] Wentao Li, A counterexample to the A060957 interpolation conjecture, 2026.
@[expose] public sectionnamespace OeisA60957Number of different products of any subset of ${1, 2, \dots, n}$.
def a (n : ℕ) : ℕ :=
((Finset.Icc 1 n).powerset.image (·.prod id)).card@[category test, AMS 5 11]
theorem a_0 : a 0 = 1 := ⊢ a 0 = 1
All goals completed! 🐙@[category test, AMS 5 11]
theorem a_1 : a 1 = 1 := ⊢ a 1 = 1
All goals completed! 🐙@[category test, AMS 5 11]
theorem a_2 : a 2 = 2 := ⊢ a 2 = 2
All goals completed! 🐙@[category test, AMS 5 11]
theorem a_3 : a 3 = 4 := ⊢ a 3 = 4
All goals completed! 🐙@[category test, AMS 5 11]
theorem a_4 : a 4 = 8 := ⊢ a 4 = 8
All goals completed! 🐙@[category test, AMS 5 11]
theorem a_5 : a 5 = 16 := ⊢ a 5 = 16
All goals completed! 🐙The set of products of subsets of ${1, \dots, n}$.
def productsOfSubsets (n : ℕ) : Set ℕ :=
{m : ℕ | ∃ s ⊆ Finset.Icc 1 n, m = s.prod id}namespace CounterexampleThe distinguished prime in the explicit circuit candidate.
def circuitPrime : ℕ := 9304595970494411110326649421962412033Auxiliary diagonal primes, arranged in six rows and twelve columns.
def circuitDiag : Fin 6 → Fin 12 → ℕ := ![
![199, 13381, 10369, 8761, 6991, 6427, 5623, 5323, 4861, 4327, 4177, 3821],
![4099, 65537, 65539, 65543, 65551, 65557, 65563, 65579, 65581, 65587, 65599, 65609],
![4111, 65617, 65629, 65633, 65647, 65651, 65657, 65677, 65687, 65699, 65701, 65707],
![4127, 65713, 65717, 65719, 65729, 65731, 65761, 65777, 65789, 65809, 65827, 65831],
![4129, 65837, 65839, 65843, 65851, 65867, 65881, 65899, 65921, 65927, 65929, 65951],
![4133, 65957, 65963, 65981, 65983, 65993, 66029, 66037, 66041, 66047, 66067, 66071]]Auxiliary primes for the eleven cross coordinates.
def circuitCross : Fin 11 → ℕ := ![3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]The coordinates of the circuit cone.
abbrev CircuitCoord := (Fin 6 × Fin 12) ⊕ Fin 11The auxiliary prime belonging to a coordinate.
def circuitAux : CircuitCoord → ℕ
| .inl ij => circuitDiag ij.1 ij.2
| .inr j => circuitCross jAll primes used in the construction, with the distinguished prime at none.
def circuitBasis : Option CircuitCoord → ℕ
| none => circuitPrime
| some q => circuitAux qA monomial in an indexed family of primes.
def primeMonomial {ι : Type*} [Fintype ι] (q : ι → ℕ) (e : ι → ℕ) : ℕ :=
∏ i, q i ^ e iThe original-domain initial-segment endpoint.
irreducible_def circuitN : ℕ := circuitPrime * 2 ^ 189All auxiliary coordinates have multiplicity two in the target core.
def circuitCoreExp : Option CircuitCoord → ℕ
| none => 0
| some _ => 2The common p-free core of the two circuit profiles.
irreducible_def circuitCore : ℕ := primeMonomial circuitBasis circuitCoreExpBalanced-base combination of finitely many additive weights.
def combinedWeight (B : ℤ) : List (ℕ → ℤ) → ℕ → ℤ
| [], _ => 0
| w :: ws, x => w x + B * combinedWeight B ws xThe rectangle constraints defining the circuit subspace.
def circuitRectWeight (i : Fin 5) (j : Fin 11) (x : ℕ) : ℤ :=
(x.factorization (circuitDiag i.succ j.succ) : ℤ) -
x.factorization (circuitDiag i.succ 0) - x.factorization (circuitDiag 0 j.succ) +
x.factorization (circuitDiag 0 0)The parity constraints make the circuit normal form integral.
def circuitCrossWeight (j : Fin 11) (x : ℕ) : ℤ :=
2 * (x.factorization (circuitCross j) : ℤ) -
x.factorization (circuitDiag 0 0) - x.factorization (circuitDiag 0 j.succ)All sixty-six defining constraints, in a fixed order.
def circuitWeights : List (ℕ → ℤ) :=
((List.finRange 5).flatMap fun i => (List.finRange 11).map (circuitRectWeight i)) ++
(List.finRange 11).map circuitCrossWeightA sufficiently large base prevents cancellation between constraint digits.
def circuitWeightBase : ℤ := 4 * (circuitN : ℤ) + 1The additive weight exposing the circuit face of the original domain.
def circuitWeight : ℕ → ℤ := combinedWeight circuitWeightBase circuitWeightsThe positive-weight factors are forced in every endpoint representation.
irreducible_def circuitPositive : Finset ℕ :=
(Finset.Icc 1 circuitN).filter (fun x => 0 < circuitWeight x)The explicit common multiplier obtained from the supporting face.
@[irreducible] def circuitMultiplier : ℕ := circuitPositive.prod idThe lower endpoint parameter in the exact counterexample.
@[irreducible] def circuitM : ℕ := circuitMultiplier * circuitCoreend Counterexample
An explicit counterexample from [Li26]: both endpoint products occur, but the intermediate
product with exponent $5$ does not. The definitions above specify every parameter, including
Counterexample.circuitM as a finite product.
@[category research solved, AMS 5 11,
formal_proof using lean4 at "https://github.com/VictorLiwentao/lean-oeis-proofs/blob/3be119e75ba5b31f034dc0c0b249975d17def711/LeanOeisProofs/NewProofs/A060957.lean#L1479"]
theorem counterexample :
Counterexample.circuitPrime.Prime ∧ Counterexample.circuitPrime ≤ Counterexample.circuitN ∧
Counterexample.circuitM ∈ productsOfSubsets Counterexample.circuitN ∧
Counterexample.circuitPrime ^ 6 * Counterexample.circuitM ∈
productsOfSubsets Counterexample.circuitN ∧
0 < (5 : ℕ) ∧ 5 < (6 : ℕ) ∧
Counterexample.circuitPrime ^ 5 * Counterexample.circuitM ∉
productsOfSubsets Counterexample.circuitN := ⊢ Nat.Prime Counterexample.circuitPrime ∧
Counterexample.circuitPrime ≤ Counterexample.circuitN ∧
Counterexample.circuitM ∈ productsOfSubsets Counterexample.circuitN ∧
Counterexample.circuitPrime ^ 6 * Counterexample.circuitM ∈ productsOfSubsets Counterexample.circuitN ∧
0 < 5 ∧
5 < 6 ∧ Counterexample.circuitPrime ^ 5 * Counterexample.circuitM ∉ productsOfSubsets Counterexample.circuitN
All goals completed! 🐙Conjecture: let $p \le n$ be prime. If $m$ and $p^a m$ are two such products, then so is $p^k m$ for all $0 < k < a$.
Yan Sheng Ang, Feb 13 2020
This interpolation conjecture is false. Disproved by Wentao Li (2026), with AI assistance; see [Li26]. The counterexample has $p = 7 \cdot 2^{120} + 1$, $n = p \cdot 2^{189}$, $a = 6$, and $k = 5$.
@[category research solved, AMS 5 11,
formal_proof using lean4 at "https://github.com/VictorLiwentao/lean-oeis-proofs/blob/3be119e75ba5b31f034dc0c0b249975d17def711/LeanOeisProofs/NewProofs/A060957.lean#L1499"]
theorem conjecture :
¬ ∀ (n p : ℕ), p.Prime → p ≤ n →
∀ (m a_exp : ℕ), m ∈ productsOfSubsets n → p ^ a_exp * m ∈ productsOfSubsets n →
∀ k : ℕ, 0 < k → k < a_exp → p ^ k * m ∈ productsOfSubsets n := ⊢ ¬∀ (n p : ℕ),
Nat.Prime p →
p ≤ n →
∀ (m a_exp : ℕ),
m ∈ productsOfSubsets n →
p ^ a_exp * m ∈ productsOfSubsets n → ∀ (k : ℕ), 0 < k → k < a_exp → p ^ k * m ∈ productsOfSubsets n
All goals completed! 🐙end OeisA60957