/-
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.
-/modulepublicimportFormalConjecturesUtil
[Gr18] Green, Ben. "A note on multiplicative functions on progressions to large moduli."
Proc. Roy. Soc. Edinburgh Sect. A 148 (2018), no. 1, 63–77. (Problem 43 is formulated here,
[Gr18, Section 4].)
[AP92] Alon, Noga, and Yuval Peres. "Uniform dilations." Geometric and Functional Analysis
2 (1992), no. 1, 1–28. (Source of the favourite variant in [Gr24, Comments to Problem 43].)
[Gr24, Comments to Problem 43] The statement that the lower bound N^{1-o(1)} holds for the
sieved set, where for each N the sieving primes range over [lo N, hi N). Problem 43 is the
case lo N = N^{0.51}, hi N = 2 N^{0.51}; the minor variants only change this range.
Let $N$ be a large integer. For each prime $p$ with $N^{0.51} \leq p < 2N^{0.51}$, pick some
residue $a(p) \in \mathbb{Z}/p\mathbb{Z}$. Is it true that
$$#{n \in [N] : n \equiv a(p) \pmod{p} \text{ for some } p} \gg N^{1-o(1)}?$$
If there is a prime p in the sieving range [lo, hi) with p ≤ N, then the sieved set is
nonempty: the residue class of a p modulo p always meets [1, N]. This shows that for large
N (where Bertrand's postulate guarantees such a prime) the cardinality in green_43 is at
least 1.
[Gr24, Comments to Problem 43; AP92] One of Green's favourite related conjectures: if
A ⊆ ℤ/pℤ is a set of size ⌊p/2⌋, does some dilation n A (n an integer) have no gaps of
length more than p^{0.49}?
The question is asymptotic, so it is stated for all sufficiently large primes p (see the
large-prime discussion in [AP92, §2]); for small primes it fails trivially, e.g. p = 3, A = {0}.
[Gr24, Comments to Problem 43] A minor variant of Problem 43: the same question but with p
ranging over N^{0.51} ≤ p < N^{0.52}. Obtaining the lower bound N^{1-o(1)} here is no harder
than Problem 43, but is not known.
[Gr24, Comments to Problem 43] One can replace the exponent 0.51 by any other exponent α:
does the lower bound N^{1-o(1)} hold for sieving primes in [N^α, 2 N^α) for every exponent
0 < α < 1? Problem 43 is the case α = 0.51; the regime α < 1/2 is the solved special case
green_43.variants.general_exponent_lt_half, while progress for α ≈ 1 would imply Kakeya.
[Gr24, Comments to Problem 43] For exponents α < 1/2 the lower bound N^{1-o(1)} is
straightforward (by an inclusion–exclusion or Cauchy–Schwarz argument). This is the solved
special case of green_43.variants.general_exponent.
@[categoryresearchsolved,AMS511]theoremgreen_43.variants.general_exponent_lt_half:∀α:ℝ,0<α→α<1/2→SievedLowerBoundExpα:=by⊢ ∀(α:ℝ),0<α→α<1/2→SievedLowerBoundExpαsorryAll goals completed! 🐙-- TODO: [Gr24, Comments to Problem 43] The toy problem (arising from a study of Problem 48):-- for each prime `p` with `X ≤ p < 2X` choose a residue `a(p) (mod p)`; for distinct primes-- `p₁, p₂` in this range let `f(p₁, p₂) ∈ ℤ/p₁p₂ℤ` be the unique CRT solution of-- `f ≡ a(pᵢ) (mod pᵢ)`. What can be said about `a` if-- `|E_{X ≤ p₁,p₂ < 2X} e(f(p₁,p₂)/(p₁ p₂))| ≥ 0.99` (more ambitiously `≥ 0.01`, or smaller)?-- Green only asks the open-ended "what can be said about `a`?", suggesting "perhaps `a` must be-- almost constant". Since "almost constant" is not made precise and a faithful encoding would-- require choosing an interpretation, this is left as a TODO to formalize.-- TODO: [Gr24, Comments to Problem 43] Green observes (unpublished) that, by arguments of-- Bourgain, progress for `α ≈ 1` would imply the Kakeya conjecture. Formalising this implication-- requires a precise statement of the Kakeya conjecture and is left for future work.-- TODO: Check the primary sources for further variants. (1) The favourite variant is "raised in-- [AP92]" (Alon–Peres, *Uniform dilations*, GAFA 1992); that paper is not freely available and-- has not been checked here for additional uniform-dilation conjectures. (2) [Gr18, Section 4]-- (where Problem 43 is formulated) raises, in the remarks to its bilinear estimate, the related-- auxiliary open problem `∑_{n ≤ X} μ(n) Λ(n - 1) = o(X)` ("the heart of the matter"). These-- are left as TODOs to formalize.endGreen43