Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Bridges_SearchOrderNoFreeLunch

Definition
Bridges_SearchOrderNoFreeLunch

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogbridges

Definition bundle for the Aether Catalog module Bridges.SearchOrderNoFreeLunch, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Bridges/SearchOrderNoFreeLunch.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Bridges_MultiTargetTrialDivision
import Definitions.Def_Bridges_TreeSieveLottery

/-!
# No fixed search order escapes the size barrier, and blind moduli are infinite

Two open items from `FUTURE_DIRECTIONS.md` are settled here, both of them
quantitative sharpenings of the round-72 verdicts.

## 1. No-free-lunch for enumeration orders (direction 4)

`MultiTargetTrialDivision.lean` proves that the *ascending* sweep first hits at
`a = min p q`, so its cost is exactly the trial-division cost.  One could hope
that a cleverer, `N`-independent order of candidate values does better.
`enumeration_defeated` shows it cannot: for **every** function `f : ℕ → ℕ` and
every prefix length `K` there are semiprimes — arbitrarily large ones — on which
the first `K` probes of `f` all miss.  The reason is structural and matches the
lottery analysis: an `N`-independent prefix is a finite set of integers, and a
finite set of integers only ever exposes the primes below its maximum.

## 2. The blind moduli form an infinite family, for every norm form (direction 3)

`NormFormBlindness.lean` shows that a search whose values are primitively
represented by `x² + D y²` has `gcd(value, N) = 1` whenever every prime factor
of `N` is inert.  Here we show that this is not a measure-zero curiosity:
by Dirichlet's theorem on primes in arithmetic progressions the set of blind
composite moduli is *infinite*, both for `D = 1` (factors `≡ 3 mod 4`,
`infinite_blindOne_semiprimes`) and for `D = 2` (factors `≡ 5 mod 8`,
`infinite_blindTwo_semiprimes`).

## 3. Capstone

`enumeration_and_hypotenuse_face_both_defeated` combines the two: given any
enumeration order and any prefix length, there is a semiprime, larger than any
prescribed bound, on which the order's whole prefix misses *and* on which the
entire (infinite) Berggren hypotenuse face has gcd `1`.  The two failure modes
are simultaneous, so trading one for the other cannot help.
-/

namespace SearchOrder

open MultiTarget TreeSieve

/-! ## Part 1 — no `N`-independent enumeration order beats the size barrier -/



/-! ## Part 2 — the blind moduli are infinite -/

/-- `N` is *blind* for the form `x² + y²`: no primitively represented value of
the form shares a factor with `N`. -/
def BlindOne (N : ℕ) : Prop :=
  ∀ a b c : ℤ, (∀ r : ℕ, r.Prime → ¬ ((r : ℤ) ∣ a ∧ (r : ℤ) ∣ b)) →
    a ^ 2 + b ^ 2 = c → Int.gcd c (N : ℤ) = 1

/-- `N` is *blind* for the form `x² + 2y²`. -/
def BlindTwo (N : ℕ) : Prop :=
  ∀ a b c : ℤ, (∀ r : ℕ, r.Prime → ¬ ((r : ℤ) ∣ a ∧ (r : ℤ) ∣ b)) →
    a ^ 2 + 2 * b ^ 2 = c → Int.gcd c (N : ℤ) = 1










/-! ## Part 3 — both failure modes strike at once -/


end SearchOrder

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me