/-
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 FormalConjecturesUtilErdős Problem 338
References:
[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
[ErGr80b] Erdős, P. and Graham, R. L., On bases with an exact order. Acta Arith. (1980), 201-207.
[HHP07] Hegyvári, Norbert and Hennecart, François and Plagne, Alain, Answer to a question by Burr and Erdős on restricted addition, and related results. Combin. Probab. Comput. (2007), 747--756.
[He05] Hennecart, François, On the restricted order of asymptotic bases of order two. Ramanujan J. (2005), 123--130.
[Ke57] Kelly, John B., Restricted bases. Amer. J. Math. (1957), 258-264.
[Pa33] Pall, Gordon, On Sums of Squares. Amer. Math. Monthly (1933), 10-18.
[Sc54] Schinzel, A., Sur la décomposition des nombres naturels en sommes de nombres triangulaires distincts. Bull. Acad. Polon. Sci. Cl. III. (1954), 409-410.
@[expose] public sectionnamespace Erdos338open Filter
HasOrder A h means that $A$ is a basis of order $h$: every sufficiently large natural number
is a sum of at most $h$ elements of $A$, with repetition allowed.
The summands form a Multiset, so repetition is allowed. Allowing at most $h$ summands makes the
notion independent of whether $0 \in A$. With exactly $h$ summands, as in
Set.IsAsymptoticAddBasisOfOrder, this notion is (insert 0 A).IsAsymptoticAddBasisOfOrder h.
def HasOrder (A : Set ℕ) (h : ℕ) : Prop :=
∀ᶠ m in atTop, ∃ S : Multiset ℕ, (∀ x ∈ S, x ∈ A) ∧ S.card ≤ h ∧ S.sum = m
HasRestrictedOrder A t means that every sufficiently large natural number is a sum of at most
$t$ distinct elements of $A$.
The summands form a Finset, so they are distinct. A summand $0$ never helps, so the notion does
not depend on whether $0 \in A$.
def HasRestrictedOrder (A : Set ℕ) (t : ℕ) : Prop :=
∀ᶠ m in atTop, ∃ S : Finset ℕ, (∀ x ∈ S, x ∈ A) ∧ S.card ≤ t ∧ ∑ x ∈ S, x = m
The order of $A$: the least $h$ with HasOrder A h, or ⊤ if $A$ is not a basis.
noncomputable def basisOrder (A : Set ℕ) : ℕ∞ :=
⨅ (h : ℕ) (_ : HasOrder A h), (h : ℕ∞)
The restricted order of $A$: the least $t$ with HasRestrictedOrder A t, or ⊤ if no such
$t$ exists.
noncomputable def restrictedOrder (A : Set ℕ) : ℕ∞ :=
⨅ (t : ℕ) (_ : HasRestrictedOrder A t), (t : ℕ∞)def erdos_338.answer : Set ℕ → Prop := sorryThe restricted order of a basis $A$ is the least integer $t$ (if it exists) such that every large integer is the sum of at most $t$ distinct summands from $A$. What are necessary and sufficient conditions that this exists?
A solution must fill in Erdos338.erdos_338.answer with the condition and prove the
equivalence. Whether a condition is a satisfactory answer is up to human judgement.
@[category research open, question value, AMS 11]
theorem erdos_338 :
∀ A : Set ℕ, (∃ h, HasOrder A h) → ((∃ t, HasRestrictedOrder A t) ↔ erdos_338.answer A) := ⊢ ∀ (A : Set ℕ), (∃ h, HasOrder A h) → ((∃ t, HasRestrictedOrder A t) ↔ erdos_338.answer A)
All goals completed! 🐙Can the restricted order of a basis be bounded (when it exists) in terms of the order of the basis?
HasOrder A h only says that the order of $A$ is at most $h$. This gives the same question,
since $f$ can be replaced by its running maximum. Kelly [Ke57] showed that $f(2) = 4$ works, and
Hennecart [He05] showed that $4$ is optimal. Hegyvári, Hennecart and Plagne [HHP07] showed that
any such $f$ has $f(k) \geq 2^{k-2}+k-1$ for $k \geq 3$.
@[category research open, question, AMS 11]
theorem erdos_338.variants.bounded_by_order :
∃ f : ℕ → ℕ, ∀ (A : Set ℕ) (h : ℕ), HasOrder A h →
(∃ t, HasRestrictedOrder A t) → HasRestrictedOrder A (f h) := ⊢ ∃ f, ∀ (A : Set ℕ) (h : ℕ), HasOrder A h → (∃ t, HasRestrictedOrder A t) → HasRestrictedOrder A (f h)
All goals completed! 🐙def erdos_338.variants.eq_order.answer : Set ℕ → Prop := sorryWhat are necessary and sufficient conditions that the restricted order of a basis $A$ is equal to the order of $A$?
For a basis, basisOrder A is finite, so the equality also says that the restricted order exists.
The condition is Erdos338.erdos_338.variants.eq_order.answer, as in Erdos338.erdos_338.
@[category research open, question value, AMS 11]
theorem erdos_338.variants.eq_order :
∀ A : Set ℕ, (∃ h, HasOrder A h) →
(restrictedOrder A = basisOrder A ↔ erdos_338.variants.eq_order.answer A) := ⊢ ∀ (A : Set ℕ), (∃ h, HasOrder A h) → (restrictedOrder A = basisOrder A ↔ eq_order.answer A)
All goals completed! 🐙Is it true that if $A \setminus F$ is a basis for all finite sets $F$ then $A$ must have a restricted order?
@[category research open, question, AMS 11]
theorem erdos_338.variants.basis_after_finite_removal :
∀ A : Set ℕ, (∀ F : Set ℕ, F.Finite → ∃ h, HasOrder (A \ F) h) →
∃ t, HasRestrictedOrder A t := ⊢ ∀ (A : Set ℕ), (∀ (F : Set ℕ), F.Finite → ∃ h, HasOrder (A \ F) h) → ∃ t, HasRestrictedOrder A t
All goals completed! 🐙Is it true that if the sets $A \setminus F$, for all finite sets $F$, are bases of the same order, then $A$ must have a restricted order?
We read "the same order" literally: every $A \setminus F$ has the same exact order $h$. This is equivalent to asking that the orders of the sets $A \setminus F$ are bounded. Removing elements can only raise the order, so if the orders are bounded, their maximum is attained at some $F_0$, and $A \setminus F_0 \subseteq A$ satisfies the literal hypothesis.
@[category research open, question, AMS 11]
theorem erdos_338.variants.same_order_after_finite_removal :
∀ A : Set ℕ,
(∃ h : ℕ, ∀ F : Set ℕ, F.Finite → basisOrder (A \ F) = (h : ℕ∞)) →
∃ t, HasRestrictedOrder A t := ⊢ ∀ (A : Set ℕ), (∃ h, ∀ (F : Set ℕ), F.Finite → basisOrder (A \ F) = ↑h) → ∃ t, HasRestrictedOrder A t
All goals completed! 🐙
If $A \setminus F$ is a basis for every finite set $F$ and $A$ has positive lower density, then
$A$ has a restricted order. So Erdos338.erdos_338.variants.basis_after_finite_removal has a
positive answer for sets of positive lower density.
This was shown by Daniel Veljjanoski on the forum (1 October 2026), with the bound $3\lceil 8/\delta^2\rceil - 2$ on the restricted order, where $\delta$ is the lower density of $A$. The linked formalisation proves the existence of a restricted order, not this bound.
@[category research solved, AMS 11, formal_proof using lean4 at
"https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-03-000016"]
theorem erdos_338.variants.lowerDensity_pos :
∀ A : Set ℕ, (∀ F : Set ℕ, F.Finite → ∃ h, HasOrder (A \ F) h) → 0 < A.lowerDensity →
∃ t, HasRestrictedOrder A t := ⊢ ∀ (A : Set ℕ), (∀ (F : Set ℕ), F.Finite → ∃ h, HasOrder (A \ F) h) → 0 < A.lowerDensity → ∃ t, HasRestrictedOrder A t
All goals completed! 🐙Bateman observed that for $h \geq 3$ the set $A = {1} \cup {x > 0 : h \mid x}$ is a basis of order $h$ with no restricted order.
@[category research solved, AMS 11]
theorem erdos_338.variants.bateman (h : ℕ) (hh : 3 ≤ h) :
basisOrder (insert 1 {x : ℕ | 0 < x ∧ h ∣ x}) = h ∧
¬ ∃ t, HasRestrictedOrder (insert 1 {x : ℕ | 0 < x ∧ h ∣ x}) t := h:ℕhh:3 ≤ h⊢ basisOrder (insert 1 {x | 0 < x ∧ h ∣ x}) = ↑h ∧ ¬∃ t, HasRestrictedOrder (insert 1 {x | 0 < x ∧ h ∣ x}) t
All goals completed! 🐙Kelly [Ke57] showed that any basis of order $2$ has restricted order at most $4$.
@[category research solved, AMS 11]
theorem erdos_338.variants.kelly (A : Set ℕ) (hA : HasOrder A 2) : HasRestrictedOrder A 4 := A:Set ℕhA:HasOrder A 2⊢ HasRestrictedOrder A 4
All goals completed! 🐙Kelly [Ke57] showed that any basis of order $2$ with positive lower density has restricted order at most $3$.
@[category research solved, AMS 11]
theorem erdos_338.variants.kelly_lowerDensity (A : Set ℕ) (hA : HasOrder A 2)
(hd : 0 < A.lowerDensity) : HasRestrictedOrder A 3 := A:Set ℕhA:HasOrder A 2hd:0 < A.lowerDensity⊢ HasRestrictedOrder A 3
All goals completed! 🐙section KellyConjecture
Ternary01 a means that all base-$3$ digits of $a$ are $0$ or $1$.
private inductive Ternary01 : ℕ → Prop
| zero : Ternary01 0
| three {a : ℕ} : Ternary01 a → Ternary01 (3 * a)
| three_add_one {a : ℕ} : Ternary01 a → Ternary01 (3 * a + 1)
The last base-$3$ digit of a is $0$ or $1$, and removing it gives a Ternary01 number.
⊢ Ternary01 0; exact .zero All goals completed! 🐙⟩
| @three a h => three a:ℕh:Ternary01 a⊢ 3 * a % 3 ≤ 1 ∧ Ternary01 (3 * a / 3) exact ⟨by a:ℕh:Ternary01 a⊢ 3 * a % 3 ≤ 1 omega All goals completed! 🐙, by a:ℕh:Ternary01 a⊢ Ternary01 (3 * a / 3) rwa [show 3 * a / 3 = a by a:ℕh:Ternary01 a⊢ Ternary01 (3 * a / 3) omega All goals completed! 🐙] a:ℕh:Ternary01 a⊢ Ternary01 a⟩
| @three_add_one a h => three_add_one a:ℕh:Ternary01 a⊢ (3 * a + 1) % 3 ≤ 1 ∧ Ternary01 ((3 * a + 1) / 3) exact ⟨by a:ℕh:Ternary01 a⊢ (3 * a + 1) % 3 ≤ 1 omega All goals completed! 🐙, by a:ℕh:Ternary01 a⊢ Ternary01 ((3 * a + 1) / 3) rwa [show (3 * a + 1) / 3 = a by a:ℕh:Ternary01 a⊢ Ternary01 ((3 * a + 1) / 3) omega All goals completed! 🐙] a:ℕh:Ternary01 a⊢ Ternary01 a⟩
Every natural number is a + b with a and b in Ternary01.
@[category API, AMS 11]
private lemma Ternary01.exists_add (k : ℕ) : ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k := by k:ℕ⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k
induction k using Nat.strong_induction_on with
| _ k ih => h k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = m⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k
rcases Nat.eq_zero_or_pos k with rfl | hk h.inl ih:∀ m < 0, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = m⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = 0h.inr k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k
· h.inl ih:∀ m < 0, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = m⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = 0 exact ⟨0, 0, .zero, .zero, rfl⟩ All goals completed! 🐙
obtain ⟨a, b, ha, hb, hab⟩ := ih (k / 3) (by k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0⊢ k / 3 < k h.inr k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k omega All goals completed! 🐙 h.inr k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k)h.inr k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k
rcases (by k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3⊢ k % 3 = 0 ∨ k % 3 = 1 ∨ k % 3 = 2 omega All goals completed! 🐙 : k % 3 = 0 ∨ k % 3 = 1 ∨ k % 3 = 2) with h | h | h
· h.inr.inl k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 0⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k exact ⟨3 * a, 3 * b, ha.three, hb.three, by k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 0⊢ 3 * a + 3 * b = k omega All goals completed! 🐙⟩
· h.inr.inr.inl k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 1⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k exact ⟨3 * a + 1, 3 * b, ha.three_add_one, hb.three, by k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 1⊢ 3 * a + 1 + 3 * b = k omega All goals completed! 🐙⟩
· h.inr.inr.inr k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 2⊢ ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = k exact ⟨3 * a + 1, 3 * b + 1, ha.three_add_one, hb.three_add_one, by k:ℕih:∀ m < k, ∃ a b, Ternary01 a ∧ Ternary01 b ∧ a + b = mhk:k > 0a:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k / 3h:k % 3 = 2⊢ 3 * a + 1 + (3 * b + 1) = k omega All goals completed! 🐙⟩
Every natural number is a + 2 * c with a and c in Ternary01.
@[category API, AMS 11]
private lemma Ternary01.exists_add_two_mul (k : ℕ) :
∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k := by k:ℕ⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k
induction k using Nat.strong_induction_on with
| _ k ih => h k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = m⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k
rcases Nat.eq_zero_or_pos k with rfl | hk h.inl ih:∀ m < 0, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = m⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = 0h.inr k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k
· h.inl ih:∀ m < 0, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = m⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = 0 exact ⟨0, 0, .zero, .zero, rfl⟩ All goals completed! 🐙
obtain ⟨a, c, ha, hc, hac⟩ := ih (k / 3) (by k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0⊢ k / 3 < k h.inr k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k omega All goals completed! 🐙 h.inr k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k)h.inr k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k
rcases (by k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3⊢ k % 3 = 0 ∨ k % 3 = 1 ∨ k % 3 = 2 omega All goals completed! 🐙 : k % 3 = 0 ∨ k % 3 = 1 ∨ k % 3 = 2) with h | h | h
· h.inr.inl k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 0⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k exact ⟨3 * a, 3 * c, ha.three, hc.three, by k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 0⊢ 3 * a + 2 * (3 * c) = k omega All goals completed! 🐙⟩
· h.inr.inr.inl k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 1⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k exact ⟨3 * a + 1, 3 * c, ha.three_add_one, hc.three, by k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 1⊢ 3 * a + 1 + 2 * (3 * c) = k omega All goals completed! 🐙⟩
· h.inr.inr.inr k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 2⊢ ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = k exact ⟨3 * a, 3 * c + 1, ha.three, hc.three_add_one, by k:ℕih:∀ m < k, ∃ a c, Ternary01 a ∧ Ternary01 c ∧ a + 2 * c = mhk:k > 0a:ℕc:ℕha:Ternary01 ahc:Ternary01 chac:a + 2 * c = k / 3h:k % 3 = 2⊢ 3 * a + 2 * (3 * c + 1) = k omega All goals completed! 🐙⟩
If a, b and c are in Ternary01 and a + b + 2 * c = 3 ^ j - 1, then a = b. All
base-$3$ digits of $3^j-1$ are $2$, and comparing last digits shows that a and b have the
same last digit.
@[category API, AMS 11]
private lemma Ternary01.eq_of_add {a b c : ℕ} (ha : Ternary01 a) (hb : Ternary01 b)
(hc : Ternary01 c) (j : ℕ) (h : a + b + 2 * c + 1 = 3 ^ j) : a = b := by a:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 cj:ℕh:a + b + 2 * c + 1 = 3 ^ j⊢ a = b
induction j generalizing a b c with
| zero => zero a:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ 0⊢ a = b rw [pow_zero zero a:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 1⊢ a = b zero a:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 1⊢ a = b] at h zero a:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 1⊢ a = b; omega All goals completed! 🐙
| succ j ih => succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ (j + 1)⊢ a = b
obtain ⟨ha3, ha'⟩ := ha.mod_div succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ (j + 1)ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)⊢ a = b
obtain ⟨hb3, hb'⟩ := hb.mod_div succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ (j + 1)ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)⊢ a = b
obtain ⟨hc3, hc'⟩ := hc.mod_div succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ (j + 1)ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)⊢ a = b
rw [pow_succ succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)⊢ a = b succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)⊢ a = b] at hsucc j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)⊢ a = b
have := ih ha' hb' hc' (by j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)⊢ a / 3 + b / 3 + 2 * (c / 3) + 1 = 3 ^ j succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)this:a / 3 = b / 3⊢ a = b omega All goals completed! 🐙succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)this:a / 3 = b / 3⊢ a = b)succ j:ℕih:∀ {a b c : ℕ}, Ternary01 a → Ternary01 b → Ternary01 c → a + b + 2 * c + 1 = 3 ^ j → a = ba:ℕb:ℕc:ℕha:Ternary01 ahb:Ternary01 bhc:Ternary01 ch:a + b + 2 * c + 1 = 3 ^ j * 3ha3:a % 3 ≤ 1ha':Ternary01 (a / 3)hb3:b % 3 ≤ 1hb':Ternary01 (b / 3)hc3:c % 3 ≤ 1hc':Ternary01 (c / 3)this:a / 3 = b / 3⊢ a = b
omega All goals completed! 🐙
The numbers 2 * a + 1 and 4 * a with a in Ternary01.
private def ternaryBasis : Set ℕ := {m | ∃ a, Ternary01 a ∧ (m = 2 * a + 1 ∨ m = 4 * a)}@[category API, AMS 11]
private lemma mem_ternaryBasis {m : ℕ} :
m ∈ ternaryBasis ↔ ∃ a, Ternary01 a ∧ (m = 2 * a + 1 ∨ m = 4 * a) :=
Iff.rfl
Every positive integer is a sum of at most two elements of ternaryBasis.
@[category API, AMS 11]
private lemma hasOrder_ternaryBasis : HasOrder ternaryBasis 2 := by ⊢ HasOrder ternaryBasis 2
unfold HasOrder ⊢ ∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = m
refine eventually_atTop.2 ⟨1, fun m hm ↦ ?_⟩ m:ℕhm:1 ≤ m⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = m
obtain ⟨k, rfl | rfl⟩ := Nat.even_or_odd' m inl k:ℕhm:1 ≤ 2 * k⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * kinr k:ℕhm:1 ≤ 2 * k + 1⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * k + 1
· inl k:ℕhm:1 ≤ 2 * k⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * k obtain ⟨a, b, ha, hb, hab⟩ := Ternary01.exists_add (k - 1) inl k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * k
refine ⟨{2 * a + 1, 2 * b + 1}, ?_, by k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ {2 * a + 1, 2 * b + 1}.card ≤ 2 simp All goals completed! 🐙, ?_⟩
· inl.refine_1 k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ ∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasis simp only [Multiset.insert_eq_cons, Multiset.mem_cons, Multiset.mem_singleton] inl.refine_1 k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ ∀ (x : ℕ), x = 2 * a + 1 ∨ x = 2 * b + 1 → x ∈ ternaryBasis
rintro x (rfl | rfl) inl.refine_1.inl k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ 2 * a + 1 ∈ ternaryBasisinl.refine_1.inr k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ 2 * b + 1 ∈ ternaryBasis
exacts [mem_ternaryBasis.2 ⟨a, ha, .inl rfl⟩, mem_ternaryBasis.2 ⟨b, hb, .inl rfl⟩] All goals completed! 🐙
· inl.refine_2 k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ {2 * a + 1, 2 * b + 1}.sum = 2 * k simp only [Multiset.insert_eq_cons, Multiset.sum_cons, Multiset.sum_singleton] inl.refine_2 k:ℕhm:1 ≤ 2 * ka:ℕb:ℕha:Ternary01 ahb:Ternary01 bhab:a + b = k - 1⊢ 2 * a + 1 + (2 * b + 1) = 2 * k
omega All goals completed! 🐙
· inr k:ℕhm:1 ≤ 2 * k + 1⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * k + 1 obtain ⟨a, c, ha, hc, rfl⟩ := Ternary01.exists_add_two_mul k inr a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 2 ∧ S.sum = 2 * (a + 2 * c) + 1
refine ⟨{2 * a + 1, 4 * c}, ?_, by a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ {2 * a + 1, 4 * c}.card ≤ 2 simp All goals completed! 🐙, ?_⟩
· inr.refine_1 a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ ∀ x ∈ {2 * a + 1, 4 * c}, x ∈ ternaryBasis simp only [Multiset.insert_eq_cons, Multiset.mem_cons, Multiset.mem_singleton] inr.refine_1 a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ ∀ (x : ℕ), x = 2 * a + 1 ∨ x = 4 * c → x ∈ ternaryBasis
rintro x (rfl | rfl) inr.refine_1.inl a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ 2 * a + 1 ∈ ternaryBasisinr.refine_1.inr a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ 4 * c ∈ ternaryBasis
exacts [mem_ternaryBasis.2 ⟨a, ha, .inl rfl⟩, mem_ternaryBasis.2 ⟨c, hc, .inr rfl⟩] All goals completed! 🐙
· inr.refine_2 a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ {2 * a + 1, 4 * c}.sum = 2 * (a + 2 * c) + 1 simp only [Multiset.insert_eq_cons, Multiset.sum_cons, Multiset.sum_singleton] inr.refine_2 a:ℕc:ℕha:Ternary01 ahc:Ternary01 chm:1 ≤ 2 * (a + 2 * c) + 1⊢ 2 * a + 1 + 4 * c = 2 * (a + 2 * c) + 1
omega All goals completed! 🐙
ternaryBasis has no restricted order $3$: no number 2 * 3 ^ j is a sum of at most three
distinct elements of ternaryBasis.
@[category API, AMS 11]
private lemma not_hasRestrictedOrder_ternaryBasis : ¬ HasRestrictedOrder ternaryBasis 3 := by ⊢ ¬HasRestrictedOrder ternaryBasis 3
intro hR hR:HasRestrictedOrder ternaryBasis 3⊢ False
unfold HasRestrictedOrder at hR hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = m⊢ False
obtain ⟨N, hN⟩ := eventually_atTop.1 hR hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = b⊢ False
obtain ⟨S, hSA, hS3, hSsum⟩ :=
hN (2 * 3 ^ N) (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = b⊢ N ≤ 2 * 3 ^ N hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False have := Nat.lt_pow_self (n := N) (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = b⊢ 1 < 3 hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bthis:N < 3 ^ N⊢ N ≤ 2 * 3 ^ N hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False norm_num All goals completed! 🐙 hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bthis:N < 3 ^ N⊢ N ≤ 2 * 3 ^ N hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False : 1 < 3) hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bthis:N < 3 ^ N⊢ N ≤ 2 * 3 ^ N hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False; omega All goals completed! 🐙 hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False) hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ False
have hP : 3 ^ N % 2 = 1 := Nat.odd_iff.1 (Odd.pow (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ N⊢ Odd 3 hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1⊢ False decide All goals completed! 🐙 hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1⊢ False)) hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishS3:S.card ≤ 3hSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1⊢ False
interval_cases h : S.card «0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False«1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 1hS3:1 ≤ 3⊢ False«2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 2hS3:2 ≤ 3⊢ False«3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 3hS3:3 ≤ 3⊢ False
· «0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False rw [Finset.card_eq_zero.1 h, «0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ ∅, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False «0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:0 = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False Finset.sum_empty «0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:0 = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False«0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:0 = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False] at hSsum«0» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:0 = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 0hS3:0 ≤ 3⊢ False
omega All goals completed! 🐙
· «1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 1hS3:1 ≤ 3⊢ False obtain ⟨x, rfl⟩ := Finset.card_eq_one.1 h «1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3x:ℕhSA:∀ x_1 ∈ {x}, x_1 ∈ ternaryBasishSsum:∑ x ∈ {x}, x = 2 * 3 ^ Nh:{x}.card = 1⊢ False
rw [Finset.sum_singleton «1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3x:ℕhSA:∀ x_1 ∈ {x}, x_1 ∈ ternaryBasishSsum:x = 2 * 3 ^ Nh:{x}.card = 1⊢ False «1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3x:ℕhSA:∀ x_1 ∈ {x}, x_1 ∈ ternaryBasishSsum:x = 2 * 3 ^ Nh:{x}.card = 1⊢ False] at hSsum«1» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3x:ℕhSA:∀ x_1 ∈ {x}, x_1 ∈ ternaryBasishSsum:x = 2 * 3 ^ Nh:{x}.card = 1⊢ False
obtain ⟨a, ha, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA x (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3x:ℕhSA:∀ x_1 ∈ {x}, x_1 ∈ ternaryBasishSsum:x = 2 * 3 ^ Nh:{x}.card = 1⊢ x ∈ {x} «1».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {2 * a + 1}, x ∈ ternaryBasishSsum:2 * a + 1 = 2 * 3 ^ Nh:{2 * a + 1}.card = 1⊢ False«1».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {4 * a}, x ∈ ternaryBasishSsum:4 * a = 2 * 3 ^ Nh:{4 * a}.card = 1⊢ False simp All goals completed! 🐙«1».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {2 * a + 1}, x ∈ ternaryBasishSsum:2 * a + 1 = 2 * 3 ^ Nh:{2 * a + 1}.card = 1⊢ False«1».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {4 * a}, x ∈ ternaryBasishSsum:4 * a = 2 * 3 ^ Nh:{4 * a}.card = 1⊢ False))«1».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {2 * a + 1}, x ∈ ternaryBasishSsum:2 * a + 1 = 2 * 3 ^ Nh:{2 * a + 1}.card = 1⊢ False«1».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {4 * a}, x ∈ ternaryBasishSsum:4 * a = 2 * 3 ^ Nh:{4 * a}.card = 1⊢ False <;> «1».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {2 * a + 1}, x ∈ ternaryBasishSsum:2 * a + 1 = 2 * 3 ^ Nh:{2 * a + 1}.card = 1⊢ False«1».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:1 ≤ 3a:ℕha:Ternary01 ahSA:∀ x ∈ {4 * a}, x ∈ ternaryBasishSsum:4 * a = 2 * 3 ^ Nh:{4 * a}.card = 1⊢ False omega All goals completed! 🐙
· «2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 2hS3:2 ≤ 3⊢ False obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.1 h «2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3x:ℕy:ℕhxy:x ≠ yhSA:∀ x_1 ∈ {x, y}, x_1 ∈ ternaryBasishSsum:∑ x ∈ {x, y}, x = 2 * 3 ^ Nh:{x, y}.card = 2⊢ False
rw [Finset.sum_pair hxy «2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3x:ℕy:ℕhxy:x ≠ yhSA:∀ x_1 ∈ {x, y}, x_1 ∈ ternaryBasishSsum:x + y = 2 * 3 ^ Nh:{x, y}.card = 2⊢ False «2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3x:ℕy:ℕhxy:x ≠ yhSA:∀ x_1 ∈ {x, y}, x_1 ∈ ternaryBasishSsum:x + y = 2 * 3 ^ Nh:{x, y}.card = 2⊢ False] at hSsum«2» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3x:ℕy:ℕhxy:x ≠ yhSA:∀ x_1 ∈ {x, y}, x_1 ∈ ternaryBasishSsum:x + y = 2 * 3 ^ Nh:{x, y}.card = 2⊢ False
obtain ⟨a, ha, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA x (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3x:ℕy:ℕhxy:x ≠ yhSA:∀ x_1 ∈ {x, y}, x_1 ∈ ternaryBasishSsum:x + y = 2 * 3 ^ Nh:{x, y}.card = 2⊢ x ∈ {x, y} «2».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhSA:∀ x ∈ {2 * a + 1, y}, x ∈ ternaryBasishSsum:2 * a + 1 + y = 2 * 3 ^ Nh:{2 * a + 1, y}.card = 2⊢ False«2».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:4 * a ≠ yhSA:∀ x ∈ {4 * a, y}, x ∈ ternaryBasishSsum:4 * a + y = 2 * 3 ^ Nh:{4 * a, y}.card = 2⊢ False simp All goals completed! 🐙«2».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhSA:∀ x ∈ {2 * a + 1, y}, x ∈ ternaryBasishSsum:2 * a + 1 + y = 2 * 3 ^ Nh:{2 * a + 1, y}.card = 2⊢ False«2».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:4 * a ≠ yhSA:∀ x ∈ {4 * a, y}, x ∈ ternaryBasishSsum:4 * a + y = 2 * 3 ^ Nh:{4 * a, y}.card = 2⊢ False))«2».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhSA:∀ x ∈ {2 * a + 1, y}, x ∈ ternaryBasishSsum:2 * a + 1 + y = 2 * 3 ^ Nh:{2 * a + 1, y}.card = 2⊢ False«2».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:4 * a ≠ yhSA:∀ x ∈ {4 * a, y}, x ∈ ternaryBasishSsum:4 * a + y = 2 * 3 ^ Nh:{4 * a, y}.card = 2⊢ False <;> «2».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhSA:∀ x ∈ {2 * a + 1, y}, x ∈ ternaryBasishSsum:2 * a + 1 + y = 2 * 3 ^ Nh:{2 * a + 1, y}.card = 2⊢ False«2».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:4 * a ≠ yhSA:∀ x ∈ {4 * a, y}, x ∈ ternaryBasishSsum:4 * a + y = 2 * 3 ^ Nh:{4 * a, y}.card = 2⊢ False
obtain ⟨b, hb, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA y (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3y:ℕa:ℕha:Ternary01 ahxy:4 * a ≠ yhSA:∀ x ∈ {4 * a, y}, x ∈ ternaryBasishSsum:4 * a + y = 2 * 3 ^ Nh:{4 * a, y}.card = 2⊢ y ∈ {4 * a, y} «2».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1}.card = 2⊢ False«2».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b}, x ∈ ternaryBasishSsum:4 * a + 4 * b = 2 * 3 ^ Nh:{4 * a, 4 * b}.card = 2⊢ False simp All goals completed! 🐙«2».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1}.card = 2⊢ False«2».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b}, x ∈ ternaryBasishSsum:4 * a + 4 * b = 2 * 3 ^ Nh:{4 * a, 4 * b}.card = 2⊢ False))«2».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1}.card = 2⊢ False«2».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b}, x ∈ ternaryBasishSsum:4 * a + 4 * b = 2 * 3 ^ Nh:{4 * a, 4 * b}.card = 2⊢ False <;> «2».inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1}.card = 2⊢ False«2».inl.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 4 * bhSA:∀ x ∈ {2 * a + 1, 4 * b}, x ∈ ternaryBasishSsum:2 * a + 1 + 4 * b = 2 * 3 ^ Nh:{2 * a + 1, 4 * b}.card = 2⊢ False«2».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1}.card = 2⊢ False«2».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b}, x ∈ ternaryBasishSsum:4 * a + 4 * b = 2 * 3 ^ Nh:{4 * a, 4 * b}.card = 2⊢ False
first
| omega All goals completed! 🐙
| (have := ha.eq_of_add hb .zero N (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1}.card = 2⊢ a + b + 2 * 0 + 1 = 3 ^ N «2».inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1}.card = 2this:a = b⊢ False omega All goals completed! 🐙«2».inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1}.card = 2this:a = b⊢ False)«2».inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:2 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1}.card = 2this:a = b⊢ False; omega All goals completed! 🐙)
· «3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bS:Finset ℕhSA:∀ x ∈ S, x ∈ ternaryBasishSsum:∑ x ∈ S, x = 2 * 3 ^ NhP:3 ^ N % 2 = 1h:S.card = 3hS3:3 ≤ 3⊢ False obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.1 h «3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:∑ x ∈ {x, y, z}, x = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False
rw [Finset.sum_insert (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:∑ x ∈ {x, y, z}, x = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ x ∉ {y, z} «3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False simp [hxy, hxz] All goals completed! 🐙«3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False), Finset.sum_pair hyz «3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False«3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False] at hSsum«3» hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ False
obtain ⟨a, ha, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA x (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3x:ℕy:ℕz:ℕhxy:x ≠ yhxz:x ≠ zhyz:y ≠ zhSA:∀ x_1 ∈ {x, y, z}, x_1 ∈ ternaryBasishSsum:x + (y + z) = 2 * 3 ^ Nh:{x, y, z}.card = 3⊢ x ∈ {x, y, z} «3».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhxz:2 * a + 1 ≠ zhSA:∀ x ∈ {2 * a + 1, y, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (y + z) = 2 * 3 ^ Nh:{2 * a + 1, y, z}.card = 3⊢ False«3».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:4 * a ≠ yhxz:4 * a ≠ zhSA:∀ x ∈ {4 * a, y, z}, x ∈ ternaryBasishSsum:4 * a + (y + z) = 2 * 3 ^ Nh:{4 * a, y, z}.card = 3⊢ False simp All goals completed! 🐙«3».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhxz:2 * a + 1 ≠ zhSA:∀ x ∈ {2 * a + 1, y, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (y + z) = 2 * 3 ^ Nh:{2 * a + 1, y, z}.card = 3⊢ False«3».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:4 * a ≠ yhxz:4 * a ≠ zhSA:∀ x ∈ {4 * a, y, z}, x ∈ ternaryBasishSsum:4 * a + (y + z) = 2 * 3 ^ Nh:{4 * a, y, z}.card = 3⊢ False))«3».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhxz:2 * a + 1 ≠ zhSA:∀ x ∈ {2 * a + 1, y, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (y + z) = 2 * 3 ^ Nh:{2 * a + 1, y, z}.card = 3⊢ False«3».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:4 * a ≠ yhxz:4 * a ≠ zhSA:∀ x ∈ {4 * a, y, z}, x ∈ ternaryBasishSsum:4 * a + (y + z) = 2 * 3 ^ Nh:{4 * a, y, z}.card = 3⊢ False <;> «3».inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:2 * a + 1 ≠ yhxz:2 * a + 1 ≠ zhSA:∀ x ∈ {2 * a + 1, y, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (y + z) = 2 * 3 ^ Nh:{2 * a + 1, y, z}.card = 3⊢ False«3».inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:4 * a ≠ yhxz:4 * a ≠ zhSA:∀ x ∈ {4 * a, y, z}, x ∈ ternaryBasishSsum:4 * a + (y + z) = 2 * 3 ^ Nh:{4 * a, y, z}.card = 3⊢ False
obtain ⟨b, hb, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA y (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3y:ℕz:ℕhyz:y ≠ za:ℕha:Ternary01 ahxy:4 * a ≠ yhxz:4 * a ≠ zhSA:∀ x ∈ {4 * a, y, z}, x ∈ ternaryBasishSsum:4 * a + (y + z) = 2 * 3 ^ Nh:{4 * a, y, z}.card = 3⊢ y ∈ {4 * a, y, z} «3».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:2 * b + 1 ≠ zhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, z}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + z) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, z}.card = 3⊢ False«3».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b, z}, x ∈ ternaryBasishSsum:4 * a + (4 * b + z) = 2 * 3 ^ Nh:{4 * a, 4 * b, z}.card = 3⊢ False simp All goals completed! 🐙«3».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:2 * b + 1 ≠ zhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, z}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + z) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, z}.card = 3⊢ False«3».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b, z}, x ∈ ternaryBasishSsum:4 * a + (4 * b + z) = 2 * 3 ^ Nh:{4 * a, 4 * b, z}.card = 3⊢ False))«3».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:2 * b + 1 ≠ zhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, z}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + z) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, z}.card = 3⊢ False«3».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b, z}, x ∈ ternaryBasishSsum:4 * a + (4 * b + z) = 2 * 3 ^ Nh:{4 * a, 4 * b, z}.card = 3⊢ False <;> «3».inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:2 * a + 1 ≠ zb:ℕhb:Ternary01 bhyz:2 * b + 1 ≠ zhxy:2 * a + 1 ≠ 2 * b + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1 + z) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1, z}.card = 3⊢ False«3».inl.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:2 * a + 1 ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:2 * a + 1 ≠ 4 * bhSA:∀ x ∈ {2 * a + 1, 4 * b, z}, x ∈ ternaryBasishSsum:2 * a + 1 + (4 * b + z) = 2 * 3 ^ Nh:{2 * a + 1, 4 * b, z}.card = 3⊢ False«3».inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:2 * b + 1 ≠ zhxy:4 * a ≠ 2 * b + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, z}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + z) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, z}.card = 3⊢ False«3».inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b, z}, x ∈ ternaryBasishSsum:4 * a + (4 * b + z) = 2 * 3 ^ Nh:{4 * a, 4 * b, z}.card = 3⊢ False
obtain ⟨c, hc, rfl | rfl⟩ := mem_ternaryBasis.1 (hSA z (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3z:ℕa:ℕha:Ternary01 ahxz:4 * a ≠ zb:ℕhb:Ternary01 bhyz:4 * b ≠ zhxy:4 * a ≠ 4 * bhSA:∀ x ∈ {4 * a, 4 * b, z}, x ∈ ternaryBasishSsum:4 * a + (4 * b + z) = 2 * 3 ^ Nh:{4 * a, 4 * b, z}.card = 3⊢ z ∈ {4 * a, 4 * b, z} «3».inr.inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:4 * b ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 4 * b, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (4 * b + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 4 * b, 2 * c + 1}.card = 3⊢ False«3».inr.inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 4 * chyz:4 * b ≠ 4 * chSA:∀ x ∈ {4 * a, 4 * b, 4 * c}, x ∈ ternaryBasishSsum:4 * a + (4 * b + 4 * c) = 2 * 3 ^ Nh:{4 * a, 4 * b, 4 * c}.card = 3⊢ False simp All goals completed! 🐙«3».inr.inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:4 * b ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 4 * b, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (4 * b + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 4 * b, 2 * c + 1}.card = 3⊢ False«3».inr.inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 4 * chyz:4 * b ≠ 4 * chSA:∀ x ∈ {4 * a, 4 * b, 4 * c}, x ∈ ternaryBasishSsum:4 * a + (4 * b + 4 * c) = 2 * 3 ^ Nh:{4 * a, 4 * b, 4 * c}.card = 3⊢ False))«3».inr.inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:4 * b ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 4 * b, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (4 * b + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 4 * b, 2 * c + 1}.card = 3⊢ False«3».inr.inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 4 * chyz:4 * b ≠ 4 * chSA:∀ x ∈ {4 * a, 4 * b, 4 * c}, x ∈ ternaryBasishSsum:4 * a + (4 * b + 4 * c) = 2 * 3 ^ Nh:{4 * a, 4 * b, 4 * c}.card = 3⊢ False <;> «3».inl.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:2 * a + 1 ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {2 * a + 1, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1, 2 * c + 1}.card = 3⊢ False«3».inl.inl.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:2 * a + 1 ≠ 4 * chyz:2 * b + 1 ≠ 4 * chSA:∀ x ∈ {2 * a + 1, 2 * b + 1, 4 * c}, x ∈ ternaryBasishSsum:2 * a + 1 + (2 * b + 1 + 4 * c) = 2 * 3 ^ Nh:{2 * a + 1, 2 * b + 1, 4 * c}.card = 3⊢ False«3».inl.inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 4 * bc:ℕhc:Ternary01 chxz:2 * a + 1 ≠ 2 * c + 1hyz:4 * b ≠ 2 * c + 1hSA:∀ x ∈ {2 * a + 1, 4 * b, 2 * c + 1}, x ∈ ternaryBasishSsum:2 * a + 1 + (4 * b + (2 * c + 1)) = 2 * 3 ^ Nh:{2 * a + 1, 4 * b, 2 * c + 1}.card = 3⊢ False«3».inl.inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:2 * a + 1 ≠ 4 * bc:ℕhc:Ternary01 chxz:2 * a + 1 ≠ 4 * chyz:4 * b ≠ 4 * chSA:∀ x ∈ {2 * a + 1, 4 * b, 4 * c}, x ∈ ternaryBasishSsum:2 * a + 1 + (4 * b + 4 * c) = 2 * 3 ^ Nh:{2 * a + 1, 4 * b, 4 * c}.card = 3⊢ False«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False«3».inr.inl.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 4 * chyz:2 * b + 1 ≠ 4 * chSA:∀ x ∈ {4 * a, 2 * b + 1, 4 * c}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + 4 * c) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 4 * c}.card = 3⊢ False«3».inr.inr.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:4 * b ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 4 * b, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (4 * b + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 4 * b, 2 * c + 1}.card = 3⊢ False«3».inr.inr.inr hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 4 * bc:ℕhc:Ternary01 chxz:4 * a ≠ 4 * chyz:4 * b ≠ 4 * chSA:∀ x ∈ {4 * a, 4 * b, 4 * c}, x ∈ ternaryBasishSsum:4 * a + (4 * b + 4 * c) = 2 * 3 ^ Nh:{4 * a, 4 * b, 4 * c}.card = 3⊢ False
first
| omega All goals completed! 🐙
| (have := ha.eq_of_add hb hc N (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ a + b + 2 * c + 1 = 3 ^ N «3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False omega All goals completed! 🐙«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False)«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False; omega All goals completed! 🐙)
| (have := ha.eq_of_add hc hb N (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ a + c + 2 * b + 1 = 3 ^ N «3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False omega All goals completed! 🐙«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False)«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ False; omega All goals completed! 🐙)
| (have := hb.eq_of_add hc ha N (by hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3⊢ b + c + 2 * a + 1 = 3 ^ N «3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3this:b = c⊢ False omega All goals completed! 🐙«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3this:b = c⊢ False)«3».inr.inl.inl hR:∀ᶠ (m : ℕ) in atTop, ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = mN:ℕhN:∀ (b : ℕ), N ≤ b → ∃ S, (∀ x ∈ S, x ∈ ternaryBasis) ∧ S.card ≤ 3 ∧ ∑ x ∈ S, x = bhP:3 ^ N % 2 = 1hS3:3 ≤ 3a:ℕha:Ternary01 ab:ℕhb:Ternary01 bhxy:4 * a ≠ 2 * b + 1c:ℕhc:Ternary01 chxz:4 * a ≠ 2 * c + 1hyz:2 * b + 1 ≠ 2 * c + 1hSA:∀ x ∈ {4 * a, 2 * b + 1, 2 * c + 1}, x ∈ ternaryBasishSsum:4 * a + (2 * b + 1 + (2 * c + 1)) = 2 * 3 ^ Nh:{4 * a, 2 * b + 1, 2 * c + 1}.card = 3this:b = c⊢ False; omega All goals completed! 🐙)end KellyConjectureKelly [Ke57] conjectured that any basis of order $2$ has restricted order at most $3$.
This was disproved by Hennecart [He05], who constructed a basis of order $2$ with restricted order $4$.
@[category research solved, question, AMS 11]
theorem erdos_338.variants.kelly_conjecture :
¬ ∀ A : Set ℕ, HasOrder A 2 → HasRestrictedOrder A 3 :=
fun h ↦ not_hasRestrictedOrder_ternaryBasis (h _ hasOrder_ternaryBasis)The set of squares has order $4$ and restricted order $5$ (see [Pa33]).
Here $0$ is a square. The order is $4$ by Lagrange's four-square theorem, and is not $3$ because no integer $\equiv 7 \pmod 8$ is a sum of three squares.
@[category research solved, AMS 11]
theorem erdos_338.variants.squares :
basisOrder (Set.range fun k : ℕ ↦ k ^ 2) = 4 ∧
restrictedOrder (Set.range fun k : ℕ ↦ k ^ 2) = 5 := by ⊢ basisOrder (Set.range fun k ↦ k ^ 2) = 4 ∧ restrictedOrder (Set.range fun k ↦ k ^ 2) = 5
sorry All goals completed! 🐙The set of triangular numbers has order $3$ and restricted order $3$ (see [Sc54]).
Here $0$ is a triangular number.
@[category research solved, AMS 11]
theorem erdos_338.variants.triangular :
basisOrder (Set.range fun k : ℕ ↦ k * (k + 1) / 2) = 3 ∧
restrictedOrder (Set.range fun k : ℕ ↦ k * (k + 1) / 2) = 3 := by ⊢ basisOrder (Set.range fun k ↦ k * (k + 1) / 2) = 3 ∧ restrictedOrder (Set.range fun k ↦ k * (k + 1) / 2) = 3
sorry All goals completed! 🐙Hegyvári, Hennecart and Plagne [HHP07] showed that for all $k \geq 2$ there exists a basis of order $k$ which has restricted order at least $2^{k-2}+k-1$.
The basis built in the proof of Theorem 4 of [HHP07] (for $k \geq 3$) has order exactly $k$ and a
finite restricted order, equal to $2^{k-2}+k-1$. The finiteness matters: without it, Bateman's
example Erdos338.erdos_338.variants.bateman would already give the bound. For $k = 2$ the bound
is $2$, and $A = {1} \cup {x : 2 \mid x}$ works.
@[category research solved, AMS 11]
theorem erdos_338.variants.hegyvari_hennecart_plagne :
∀ k : ℕ, 2 ≤ k → ∃ A : Set ℕ,
basisOrder A = k ∧ restrictedOrder A = (2 ^ (k - 2) + k - 1 : ℕ) := by ⊢ ∀ (k : ℕ), 2 ≤ k → ∃ A, basisOrder A = ↑k ∧ restrictedOrder A = ↑(2 ^ (k - 2) + k - 1)
sorry All goals completed! 🐙end Erdos338