A remark on dimensionality reduction in discrete subgroups

Rodolfo Viera

REVIEW 4 major objections 4 minor 10 references

A remark on dimensionality reduction in discrete subgroups

T0 review · 4 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Discrete subgroups admit JL flattening into $O(\varepsilon^{-2}\log d)$ dimensions.

desk verdict A genuinely new combination of ideas, but the proof's scaling error leaves the main proposition unproven. read the letter →

arxiv 2501.01396 v3 pith:C75ZEEHD submitted 2025-01-02 math.MG

Rodolfo Viera This is my paper · ORCID

classification math.MG MSC 46B85

keywords Johnson–LindenstrausslemmadiscretesubgrouplatticeembeddingdimensionalityreductionmetricdistortionuniformdistributionmodulooneZiegler'stheoremquantizeddata

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims a discrete version of the Johnson–Lindenstrauss lemma for point sets that live in a fine lattice $\frac{\lambda}{\lambda_0}\mathbb{Z}^d$ inside a ball of radius $\lambda N_0$. After the lattice is scaled by a sufficiently large integer $\lambda$, any $d$ such points can be mapped into the coarser grid $\frac{1}{\lambda_0}\mathbb{Z}^k$, where $k=O(\varepsilon^{-2}\log d)$, with pairwise distances preserved up to a factor $1+\varepsilon+\frac{\varepsilon}{\lambda\lambda_0}$. The result matters because realistic high-dimensional data is quantised rather than continuous, and this says the classical flattening can be adapted to respect the grid structure while keeping both the number of decimals and the magnitude of the output bounded.

What carries the argument

The argument is carried by three ingredients. The Johnson–Lindenstrauss lemma provides a linear map $\Phi:\mathbb{R}^d\to\mathbb{R}^k$ that is an $(1+\varepsilon)$-embedding on the input points. Ziegler's theorem supplies, for each sufficiently large dilation $l$, a rotation $\rho\in SO(k)$ such that the dilates of the projected points are within $\varepsilon$ of $\mathbb{Z}^k$; this is the step that forces the large scale $\lambda$. A one-dimensional uniform-distribution lemma for irrational $t$ guarantees that dilations of $t\mathbb{Z}$ modulo $1$ are dense, which is used to find the admissible scale $\lambda_1$. The final map $F$ sends a point $\lambda x_i$ to the nearest point of $\frac{1}{\lambda_0}\mathbb{Z}^k$ after the rotation $\rho$ is applied.

What would settle it

For $\lambda_0=2$ and $\varepsilon=1/4$, take two points in $D$ at the minimal lattice separation $\lambda/\lambda_0$ apart. Substituting the unscaled distance $\|x_i-x_j\|=1/\lambda_0$ into the proof's inequality (2.3) reduces its last step to the requirement $\varepsilon\le \varepsilon/\lambda_0^2$, which is false for $\lambda_0>1$; checking (1.1) for this pair therefore settles whether the claimed uniform distortion holds for all pairs.

Watch

Extended reading notes

Core claim

The central discovery is that a Johnson–Lindenstrauss projection can be composed with a rotation and a rounding step so that the output lies exactly on a prescribed grid, with the quantisation error absorbed by a large dilation of the input lattice. Concretely, the author proves that for every $d,\lambda_0,N_0\in\mathbb{N}$ and $\varepsilon\in(0,\frac{1}{\lambda_0+1})$ there is a dimension $k=O(\varepsilon^{-2}\log d)$ such that, once $\lambda$ is taken large enough, any $d$-point set in $\frac{\lambda}{\lambda_0}\mathbb{Z}^d\cap B(0,\lambda N_0)$ admits a map $F$ into $\frac{1}{\lambda_0}\mathbb{Z}^k$ satisfying the two-sided distortion bound for all pairs. The construction uses the classical JL lemma, Ziegler's theorem on rotating dilated finite sets close to the integer lattice, and a uniform-distribution lemma to justify the existence of the dilation scale.

Load-bearing premise

The proof depends on comparing the upper bound measured on the dilated points $\lambda x$ with the lower bound measured on the original points $x$, assuming these two measurements are on the same scale; if the factor $\lambda$ separates them, the chained inequality cannot yield the claimed uniform distortion.

Editorial extensions

If this is right

If the main proposition is correct, any finite data set confined to a sufficiently fine lattice can be embedded into a coarser lattice of dimension $O(\varepsilon^{-2}\log d)$ with near-isometric distortion.
The distortion bound tends to $1+\varepsilon$ as $\lambda\to\infty$, so the discrete constraint becomes asymptotically costless in the large-scale limit.
The output lies in $\frac{1}{\lambda_0}\mathbb{Z}^k$, which means the embedded vectors have bounded magnitude and fixed decimal precision, matching the constraints of a quantised computational model.
The dimension $k$ is independent of the ambient dimension $d$, so the reduction can be dramatic when $d\gg\log d$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the scaling gap in the proof can be closed, a constructive version with explicit $\lambda_1$ would give a fully discrete JL transform usable in practice on quantised data.
The dependence on Ziegler's theorem suggests the embedding is non-constructive; obtaining it algorithmically may require an effective uniform-distribution statement.
A natural test is whether the theorem survives when $\varepsilon$ is allowed to be larger than $1/(\lambda_0+1)$; the current restriction couples distortion to grid coarseness.
The argument may extend to other discrete subgroups, such as weighted integer lattices, provided an analogue of Ziegler's rotation theorem holds there.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main take: the paper's idea is new, but the proof as written does not establish the stated result. The construction works on a scaled copy of the point set, and the upper and lower bounds are normalized at incompatible scales. That is a load-bearing error, not a typo.

What's actually new: Viera proposes a discrete-subgroup version of the JL lemma, targeting a lattice (1/λ0)Z^k, and brings two tools to bear: Ziegler's rotation theorem and uniform distribution modulo 1. The explicit error term ε/(λλ0) and the use of a large scaling λ are a reasonable way to get integer-valued embeddings. The combination is not in the cited literature, and the author does not oversell it as a new framework.

The soft spot: the proof of Proposition 1.1 defines F on λD, not D. Equation (2.3) bounds (1/λ0)‖z_i−z_j‖ by (1+ε+ε/(λλ0))‖λx_i−λx_j‖, which is a factor λ larger than the upper bound required in (1.1). Equation (2.4) is stated relative to ‖x_i−x_j‖. So the two inequalities cannot be chained to give (1.1). If you rescale z_i to force the upper bound to match (1.1), the target lattice becomes (1/(λλ0))Z^k and the lower bound picks up an extra 1/λ. The main claim is therefore unsupported. There are also smaller issues: Lemma 2.1 is deferred to [2] for the hard part, the reference to a {0,1}-matrix JL transform is not standard (usually ±1), and the claim that Dflat lies in (1/λ0)√k Z^k appears to be off by a factor λ.

On the plus side, the paper is short and honest; it cites the right literature and does not hide its reliance on Ziegler and uniform distribution. It is just the central chain that fails.

If you are deciding whether to referee it: I would say it deserves a look, but with the expectation that the author needs to either fix the scaling, which may be possible by redefining the target lattice, or substantially revise the statement. As it stands, I would not accept the proof. For a reading group, it is a reasonable example of how scaling errors creep into JL-style proofs. I would not cite it yet.

Referee Report

4 major / 4 minor

Summary. The paper proposes a discrete version of the Johnson-Lindenstrauss lemma: for point sets lying in the lattice (λ/λ0)Z^d and in a ball of radius λN0, it claims the existence of an embedding into (1/λ0)Z^k with dimension k = O(ε^{-2} log d) and distortion close to 1. The proof combines the classical JL lemma with a theorem of T. Ziegler on rotating dilated finite sets near the integer lattice, together with a rounding step into (1/λ0)Z^k. The central assertion is Proposition 1.1, and the proof is contained in Section 2.

Significance. If the main proposition were correct, it would provide a natural discrete counterpart to JL dimensionality reduction, with the target space constrained to a lattice of the same spacing as the input lattice. The question is interesting and the chosen tools (JL, Ziegler's theorem, uniform distribution) are relevant. However, the proof as written contains a fundamental scaling error: the map is constructed on the dilated set λD while the theorem requires a map on D. The result may still be salvageable with a corrected target lattice or a reformulated distortion bound, but the current manuscript does not establish the stated claim. There are no machine-checked proofs or reproducible code in the paper.

major comments (4)

[§2, above (2.3)] The map F is defined as F: λx_i ↦ (1/λ0) z_i, i.e., on the dilated set λD, whereas Proposition 1.1 requires F: D → (1/λ0)Z^k. Consequently, equation (2.3) bounds (1/λ0)‖z_i−z_j‖ in terms of ‖λx_i−λx_j‖, which is λ times the norm ‖x_i−x_j‖ appearing in (1.1). Equation (2.4) provides a lower bound relative to ‖x_i−x_j‖, so the two inequalities are normalized at incompatible scales. Writing G(x) = F(λx) for x∈D, equations (2.3)–(2.4) yield λ(1−ε−ε/(λλ0))‖x_i−x_j‖ ≤ ‖G(x_i)−G(x_j)‖ ≤ λ(1+ε+ε/(λλ0))‖x_i−x_j‖ (up to additive ε terms), not the constant-factor distortion claimed in (1.1). The proof therefore does not establish the proposition as stated.
[§2, paragraph on Dflat] The claim that Dflat is a subset of (1/λ0)√k Z^k, based on Φ(x) = (1/√k) R x^T with R an {0,1}-valued matrix, omits the factor λ: since x_i ∈ (λ/λ0)Z^d, the image coordinates lie in (λ/(λ0√k))Z, not (1/(λ0√k))Z. This is the same scaling error in a different location and further affects the subsequent application of Ziegler's theorem and the rounding step.
[Lemma 2.1] The lemma states that for every λ ≥ λ1 there is a rotation ρ with d(ρ(λD), Z^k) < ε for all D ⊂ tZ^k ∩ B_N. The proof, however, only produces a single integer n1 such that d(n1D, Z^k) < ε, and then says the rest follows as in [2]. No argument is given for the uniformity in λ ≥ λ1, and the proof does not establish the lemma as stated. Since Lemma 2.1 is a load-bearing ingredient in the proof of the main proposition, this is a significant gap.
[§2, use of Ziegler's Theorem] The proof asserts, by Ziegler's Theorem and Lemma 2, that there exists λ1 depending only on ε,k,N0 such that for all λ ≥ λ1 there is a rotation ρ with d(ρ(λDflat), (1/λ0)Z^k) ≤ ε/λ0. Ziegler's Theorem provides large integer multiples of a fixed finite set close to the lattice; here the set λ0Dflat depends on λ through the factor λ in the lattice spacing of Dflat. The threshold λ1 therefore may need to depend on Dflat (i.e., on the particular point set D), but the proposition requires a λ1 that works uniformly for all λ ≥ λ1 for each fixed D. This uniformity is not justified, and no proof is supplied.

minor comments (4)

[Abstract] The abstract contains typos such as 'Johnson-Lindenstra uss flattening' and the phrase 'suitably chosen' for ε is vague; the hypotheses on ε and on the parameters deserve precise statements.
[§2, equation (2.3)] The final inequality in (2.3) appears to require that ε ≤ (ε/λ0)‖x_i−x_j‖, which uses the minimum spacing of points in D. This is not stated or proved; it may hold for sufficiently large λ, but the justification is missing.
[§2, ] The phrase 'since a translation by a vector is an isometry, we can assume the origin of R^k is the circumcenter of Dflat' requires justification that the translation preserves the lattice property of the point set; not all translations preserve the membership in (λ/(λ0√k))Z^k.
[References] Reference [5] appears garbled ('M. K/suppress lopotek'); this should be corrected to the actual author name.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the proof uses independent external theorems (JL, Ziegler, uniform distribution) and does not presuppose its conclusion.

full rationale

The paper's derivation chain is built from external, non-self-cited results: the Johnson-Lindenstrauss lemma, Ziegler's theorem on approximate lattice embeddings under rotations, and uniform distribution modulo 1. The Main Proposition's conclusion (1.1) is not assumed anywhere in the proof; instead it is derived by combining the JL embedding with a rotation supplied by Ziegler's theorem. No parameter is fitted to the target data and then renamed as a prediction; epsilon and lambda0 are fixed inputs and lambda is chosen existentially from the external lemmas. The author does not cite his own prior work, and no uniqueness theorem is imported from the same authors. A reader's concern about a possible scaling mismatch between equations (2.3) and (2.4) is a question of mathematical correctness of the proof's final inequality, not a circularity in which an input is equivalent to the output by definition. Since the paper is self-contained against external benchmarks and no step reduces to its own inputs, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on three external results (JL, Ziegler's theorem, uniform distribution) plus a specific integer-entry JL variant. No fitted parameters or new entities are introduced.

assumptions (5)

standard math Johnson-Lindenstrauss lemma for finite point sets
Invoked in the proof of the Main Proposition to map D to R^k with distortion at most (1+ε).
standard math Ziegler's theorem (Theorem 1.2)
Used to find a rotation ρ(λ) such that ρ(λ Dflat) is within ε/λ0 of (1/λ0)Z^k.
standard math Uniform distribution modulo 1 of irrational multiples
Used in Lemma 2.1 to find an integer n1 with |n1 t − p| < ε/N.
domain assumption Existence of a JL embedding with integer matrix entries in {0,1}
The proof requires Φ(x) = (1/√k) R x with R a d×k matrix with entries in {0,1} so that Dflat lies in a scaled lattice; this is cited to [7] but not standard and not verified.
domain assumption Minimal separation of distinct lattice points in (λ/λ0)Z^d is λ/λ0
Used to justify the final inequality in (2.3) requiring ‖x_i − x_j‖ ≥ λ0.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A remark on dimensionality reduction in discrete subgroups." pith.science (2026). https://pith.science/paper/C75ZEEHD

@misc{pith2026250101396,
  author       = {Pith},
  title        = {Pith review of: A remark on dimensionality reduction in discrete subgroups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C75ZEEHD}},
  note         = {Machine review of arXiv:2501.01396}
}

abstract

In this short note, we prove a version of the Johnson-Lindenstrauss flattening Lemma for point sets taking values in discrete subgroups. More precisely, given $d,\lambda_0,N_0\in\mathbb{N}$ and $\epsilon\in \left(0,\frac{1}{2}\right)$ suitably chosen, we show there exists a natural number $k=k(d,\epsilon)=O\left(\frac{1}{\epsilon^2}\log d\right)$, such that for every sufficiently large scaling factor $\lambda\in\mathbb{N}$ and any point set $\mathcal{D}\subset\frac{\lambda}{\lambda_0}\mathbb{Z}^d\cap B(0,\lambda N_0)$ with cardinality $d$, there exists an embedding $F:\mathcal{D}\to\frac{1}{\lambda_0}\mathbb{Z}^k$, with distortion at most $\left(1+\epsilon+\frac{\epsilon}{\lambda\lambda_0}\right)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[2]

Approximate embedding of large polygons into $Z^2$

M. Boshernitzan, Approximate embedding of large polygons into ^2 , ArXiv:1208.1026v2 , 2012

work page Pith review arXiv 2012
[1]

Achlioptas, Database-friendly random projections, Proc

D. Achlioptas, Database-friendly random projections, Proc. of the 20th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of database systems , 274-281, 2001

work page 2001
[3]

Gromov, Metric structures for Riemannian and non-Riemannian spaces

M. Gromov, Metric structures for Riemannian and non-Riemannian spaces . Birkh\" a user Boston, Vol. 152 , 1999

work page 1999
[4]

Freksen, An introduction to Johnson-Lindenstrauss transforms, ArXiv:2103.00564 , 2021

C.B. Freksen, An introduction to Johnson-Lindenstrauss transforms, ArXiv:2103.00564 , 2021

arXiv 2021
[5]

Johnson and J

W.B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space. In: Conference in modern analysis and probability (New Haven, Conn.1 1982) . Vol. 26. Contemp. Math. Providence, RI: Amer. Math. Soc., 189-206, 1984

work page 1982
[6]

Kłopotek, Machine learning friendly set version of Johnson–Lindenstrauss lemma, Knowledge and Information Systems, 62(5) : 1961-2009, 2020

M. Kłopotek, Machine learning friendly set version of Johnson–Lindenstrauss lemma, Knowledge and Information Systems, 62(5) : 1961-2009, 2020

work page 1961
[7]

Kuipers and H

L. Kuipers and H. Niederreiter, Uniform distribution of sequences . Wiley, New York, 1974

work page 1974
[8]

Matou s ek, On variants of the Johnson–Lindenstrauss lemma, Random Struct

J. Matou s ek, On variants of the Johnson–Lindenstrauss lemma, Random Struct. Algorithms, 33(2) : 142–156, 2008

work page 2008

Show all 10 references

[9]

M. I. Ostrovskii, Metric embeddings: bilipschitz and coarse embeddings into Banach spaces . First edition, Studies in Math., De Gruyter, 2013

2013
[10]

Ziegler, Nilfactors of ^m -actions and configurations in sets of positive upper density in ^m , J

T. Ziegler, Nilfactors of ^m -actions and configurations in sets of positive upper density in ^m , J. Anal. Math. , 99 , 249-266, 2006

2006

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [2]

Approximate embedding of large polygons into $Z^2$

M. Boshernitzan, Approximate embedding of large polygons into ^2 , ArXiv:1208.1026v2 , 2012

work page Pith review arXiv 2012

[2] [1]

Achlioptas, Database-friendly random projections, Proc

D. Achlioptas, Database-friendly random projections, Proc. of the 20th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of database systems , 274-281, 2001

work page 2001

[3] [3]

Gromov, Metric structures for Riemannian and non-Riemannian spaces

M. Gromov, Metric structures for Riemannian and non-Riemannian spaces . Birkh\" a user Boston, Vol. 152 , 1999

work page 1999

[4] [4]

Freksen, An introduction to Johnson-Lindenstrauss transforms, ArXiv:2103.00564 , 2021

C.B. Freksen, An introduction to Johnson-Lindenstrauss transforms, ArXiv:2103.00564 , 2021

arXiv 2021

[5] [5]

Johnson and J

W.B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space. In: Conference in modern analysis and probability (New Haven, Conn.1 1982) . Vol. 26. Contemp. Math. Providence, RI: Amer. Math. Soc., 189-206, 1984

work page 1982

[6] [6]

Kłopotek, Machine learning friendly set version of Johnson–Lindenstrauss lemma, Knowledge and Information Systems, 62(5) : 1961-2009, 2020

M. Kłopotek, Machine learning friendly set version of Johnson–Lindenstrauss lemma, Knowledge and Information Systems, 62(5) : 1961-2009, 2020

work page 1961

[7] [7]

Kuipers and H

L. Kuipers and H. Niederreiter, Uniform distribution of sequences . Wiley, New York, 1974

work page 1974

[8] [8]

Matou s ek, On variants of the Johnson–Lindenstrauss lemma, Random Struct

J. Matou s ek, On variants of the Johnson–Lindenstrauss lemma, Random Struct. Algorithms, 33(2) : 142–156, 2008

work page 2008