On discrepancy estimates for pseudorandom vectors constructed by the elliptic curve congruential generator

Chung Pang Mok; Ziran Liu

arxiv: 2605.20627 · v1 · pith:SFCQCJ3Vnew · submitted 2026-05-20 · 🧮 math.NT

On discrepancy estimates for pseudorandom vectors constructed by the elliptic curve congruential generator

Ziran Liu , Chung Pang Mok This is my paper

Pith reviewed 2026-05-21 03:03 UTC · model grok-4.3

classification 🧮 math.NT

keywords discrepancy estimatespseudorandom vectorselliptic curve congruential generatorlinear congruential generatoruniform distributionFourier analysisnumber theory

0 comments

The pith

Under a relative maximal period condition on an induced linear congruential generator, the elliptic curve congruential generator produces pseudorandom vectors with discrepancy at most q to the one-half power over t.

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

This paper studies discrepancy estimates for pseudorandom vectors from the elliptic curve congruential generator in the non-translational case. In the full-coset regime where the relative maximal period condition holds for the induced one-dimensional linear congruential generator, it proves bounds of order q to the power one half over t for the discrepancy, serial discrepancy, and non-overlapping discrepancy. A sympathetic reader would care because such bounds indicate how uniformly the generated points are distributed, which is key for their effectiveness as pseudorandom sources in numerical methods and simulations. In the general case, it reduces the discrepancy problem to estimating Fourier l1 masses of certain index sets attached to linear generators.

Core claim

In a full-coset regime characterized by a relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator, bounds of type q^{1/2}/t are proved for the discrepancy D, the serial discrepancy D_s, and under the corresponding derived RMPC, the non-overlapping discrepancy ~D_s. In the general sub-period regime, bounds for D, D_s, and ~D_s reduce to estimation of Fourier ell^1 masses of admissible index sets attached to one-dimensional linear congruential generators.

What carries the argument

The relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator, which characterizes the full-coset regime and supports the proof of the q^{1/2}/t discrepancy bounds.

If this is right

The generated vectors exhibit low discrepancy in one and higher dimensions when the condition is met.
Similar bounds apply to serial and non-overlapping versions of the discrepancy.
The general case isolates the problem to Fourier l1 mass estimates for further improvement.
These results extend discrepancy analysis from linear to elliptic curve based generators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Verifying the RMPC for specific elliptic curves could enable practical selection of good generators.
The reduction to Fourier masses suggests links to exponential sum estimates in number theory.
Extensions might include multidimensional versions or other curve families.

Load-bearing premise

The relative maximal period condition holds for the induced one-dimensional linear congruential generator defining the full-coset regime.

What would settle it

Select an elliptic curve and generator parameters that satisfy the relative maximal period condition, generate the vectors, compute their discrepancy numerically for large q, and verify if the value exceeds or stays below the q^{1/2}/t bound.

read the original abstract

This paper studies the problem of discrepancy estimates for pseudorandom vectors constructed by the elliptic curve congruential generator, particularly in the non-translational case. Two families of results are obtained. First, in a full-coset regime characterized by a relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator, one proves bounds of type $q^{1/2}/t$ for the discrepancy $D$, the serial discrepancy $D_s$, and, under the corresponding derived RMPC, the non-overlapping discrepancy $\widetilde D_s$. Second, in the general sub-period regime, one reduces bounds for $D$, $D_s$, and $\widetilde D_s$ to estimation of Fourier $\ell^1$ masses of admissible index sets attached to one-dimensional linear congruential generators. This isolates the arithmetic bottleneck for further improvement.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The q^{1/2}/t bounds are conditional on an RMPC that the paper does not verify for the elliptic-curve case, while the Fourier l1 reduction is the clearer contribution.

read the letter

The headline result here is a set of discrepancy bounds of size q^{1/2}/t for the non-translational elliptic curve congruential generator, but these hold only inside the full-coset regime defined by the relative maximal period condition on the induced one-dimensional LCG. The paper does not show that this condition is met for the admissible index sets coming from the elliptic curve, so the quantitative statements stay conditional on an arithmetic hypothesis whose frequency is left open. That matches the stress-test concern exactly, and it limits how far the bounds can be used right now for actual pseudorandom generation. On the other side, the paper does two things cleanly. It extends the earlier discrepancy work to the non-translational setting, and it reduces the general sub-period case to the problem of bounding the Fourier l1 mass of certain admissible index sets attached to linear congruential generators. That reduction isolates the remaining arithmetic bottleneck without circularity, which is useful even if the mass estimates themselves are not carried out. The methods are standard discrepancy plus Fourier analysis, so the derivations look reproducible in principle once the full proofs are checked. The soft spot is precisely the unverified RMPC; everything else is proportionate to what is claimed. This paper is for specialists in uniform distribution theory and pseudorandom number generation who already work with elliptic or linear constructions. A reader who wants to improve the arithmetic estimates on those index sets will find the reduction helpful. I would send it to peer review because the reduction is a concrete step forward and the conditional bounds are stated without overclaim. Referees can verify the calculations and see whether the RMPC can be addressed or replaced.

Referee Report

2 major / 1 minor

Summary. The paper studies discrepancy estimates for pseudorandom vectors from the elliptic curve congruential generator in the non-translational case. It proves bounds of type q^{1/2}/t for the discrepancy D, serial discrepancy D_s, and non-overlapping discrepancy ~D_s in a full-coset regime defined by a relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator. In the general sub-period regime, it reduces bounds for D, D_s, and ~D_s to estimates of the Fourier ℓ¹ masses of admissible index sets attached to one-dimensional linear congruential generators, thereby isolating the arithmetic bottleneck.

Significance. If the derivations hold, the work supplies a structured approach to discrepancy analysis for elliptic-curve-based generators by separating the full-coset case (where explicit q^{1/2}/t bounds are obtained) from the general case (where the problem is reduced to a concrete Fourier-analytic task). The clean isolation of the RMPC hypothesis and the reduction to ℓ¹-mass estimates constitute a useful technical contribution that can guide subsequent verification or construction of index sets satisfying the required arithmetic conditions.

major comments (2)

[Abstract] Abstract and the statement of the main results: the quantitative bounds of type q^{1/2}/t for D, D_s and ~D_s are established exclusively inside the full-coset regime defined by the RMPC on the induced LCG. The manuscript does not prove that this RMPC is attained (or attained with positive density) for the admissible index sets produced by the elliptic-curve construction, nor does it supply explicit examples or density estimates. Consequently the headline bounds remain conditional on an arithmetic hypothesis whose validity is left open.
[General sub-period regime (as described in abstract)] The reduction in the sub-period regime: while the reduction of discrepancy bounds to Fourier ℓ¹-mass estimates of admissible index sets is formally correct as a separation of concerns, the paper does not indicate whether these masses can be bounded non-trivially for the specific index sets arising from the elliptic-curve generator, leaving the practical utility of the reduction dependent on future arithmetic work.

minor comments (1)

[Abstract] Notation: the parameters q and t are used without explicit definition in the abstract; a brief reminder of their meaning (field size and period parameter, respectively) would improve readability.

Simulated Author's Rebuttal

2 responses · 2 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We respond to each major comment below, indicating revisions where appropriate to improve clarity while preserving the scope of the results.

read point-by-point responses

Referee: [Abstract] Abstract and the statement of the main results: the quantitative bounds of type q^{1/2}/t for D, D_s and ~D_s are established exclusively inside the full-coset regime defined by the RMPC on the induced LCG. The manuscript does not prove that this RMPC is attained (or attained with positive density) for the admissible index sets produced by the elliptic-curve construction, nor does it supply explicit examples or density estimates. Consequently the headline bounds remain conditional on an arithmetic hypothesis whose validity is left open.

Authors: We agree that the q^{1/2}/t bounds are established conditionally on the RMPC holding for the induced one-dimensional LCG. The manuscript derives these bounds under that hypothesis and does not attempt to prove attainment or positive density for the elliptic-curve index sets, as that would require separate arithmetic work on the specific admissible sets. We will revise the abstract and add a clarifying paragraph in the introduction to state explicitly that the bounds are conditional on the RMPC and to note that verifying this condition for the constructions remains open. This addresses the presentation concern without changing the technical results. revision: partial
Referee: [General sub-period regime (as described in abstract)] The reduction in the sub-period regime: while the reduction of discrepancy bounds to Fourier ℓ¹-mass estimates of admissible index sets is formally correct as a separation of concerns, the paper does not indicate whether these masses can be bounded non-trivially for the specific index sets arising from the elliptic-curve generator, leaving the practical utility of the reduction dependent on future arithmetic work.

Authors: The reduction is designed precisely to isolate the remaining arithmetic task of bounding the Fourier ℓ¹ masses on the admissible index sets attached to the induced LCGs. We do not claim non-trivial bounds for the elliptic-curve-specific sets in this paper. To better indicate the utility, we will add a short remark in the relevant section outlining possible approaches to such bounds (e.g., via character-sum techniques or properties of the underlying elliptic curve) and explicitly framing this as a direction for subsequent work. This strengthens the separation-of-concerns contribution without extending the current proofs. revision: partial

standing simulated objections not resolved

Proving that the RMPC holds (or holds with positive density) for the admissible index sets arising from the elliptic-curve congruential generator.
Deriving non-trivial bounds on the Fourier ℓ¹ masses for the specific admissible index sets in the general sub-period regime.

Circularity Check

0 steps flagged

No circularity: bounds derived under explicit RMPC hypothesis via standard Fourier/discrepancy methods; general case reduced to independent arithmetic estimates

full rationale

The paper establishes q^{1/2}/t-type bounds for discrepancy quantities exclusively inside the full-coset regime defined by the relative maximal period condition (RMPC) on the induced one-dimensional LCG, using standard techniques from discrepancy theory and Fourier analysis. In the sub-period regime it reduces the problem to bounding Fourier ℓ¹ masses of admissible index sets, thereby isolating an open arithmetic question rather than presupposing its resolution. No equation equates a claimed prediction to a fitted input by construction, no load-bearing step collapses to a self-citation chain, and RMPC is introduced as an explicit arithmetic hypothesis rather than a self-definitional tautology. The derivation chain therefore remains self-contained against external number-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard results from discrepancy theory, uniform distribution modulo 1, and elliptic curve arithmetic over finite fields; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)

standard math Standard bounds and properties from discrepancy theory and Fourier analysis on finite fields.
The paper invokes these to derive the stated estimates and reductions.

pith-pipeline@v0.9.0 · 5677 in / 1311 out tokens · 47940 ms · 2026-05-21T03:03:59.479807+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat recovery; embed_injective unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

bounds of type q^{1/2}/t for the discrepancy D, the serial discrepancy D_s, and ... non-overlapping discrepancy ~D_s ... under the relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

reduces bounds for D, D_s, and ~D_s to estimation of Fourier ℓ¹ masses of admissible index sets attached to one-dimensional linear congruential generators

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

C. P. Mok, Pseudorandom vector generation using elliptic curves and applications to Wiener processes,Finite Fields Appl.85(2023), 102129

work page 2023
[2]

C. P. Mok, H. Zheng, Monte Carlo Integration Using Elliptic Curves,Chin. Ann. Math. Ser. B.46(2) (2025), 241–260

work page 2025
[3]

Wang, On the distribution of pseudorandom vectors generated by elliptic curves,Finite Fields Appl.93(2024), 102318

X. Wang, On the distribution of pseudorandom vectors generated by elliptic curves,Finite Fields Appl.93(2024), 102318. 29

work page 2024
[4]

Hellekalek, General discrepancy estimates: the Walsh function system,Acta Arith.LXVII (3) (1994), 209–218

P. Hellekalek, General discrepancy estimates: the Walsh function system,Acta Arith.LXVII (3) (1994), 209–218

work page 1994
[5]

Kohel, I

D. Kohel, I. Shparlinski, On exponential sums and group generators for elliptic curves over finite fields, Proc. the 4th Algorithmic Number Theory Symp., in: Lecture Notes in Comput. Sci., vol. 1838, Springer-Verlag, Berlin, 2000, pp. 395–404

work page 2000
[6]

I. E. Shparlinski, Bilinear character sums over elliptic curves,Finite Fields Appl.14(2008), 132–141

work page 2008
[7]

Ahmadi and I

O. Ahmadi and I. E. Shparlinski, Bilinear character sums and sum-product problems on elliptic curves,Proc. Edinburgh Math. Soc.53(2010), 1–12. 30

work page 2010

[1] [1]

C. P. Mok, Pseudorandom vector generation using elliptic curves and applications to Wiener processes,Finite Fields Appl.85(2023), 102129

work page 2023

[2] [2]

C. P. Mok, H. Zheng, Monte Carlo Integration Using Elliptic Curves,Chin. Ann. Math. Ser. B.46(2) (2025), 241–260

work page 2025

[3] [3]

Wang, On the distribution of pseudorandom vectors generated by elliptic curves,Finite Fields Appl.93(2024), 102318

X. Wang, On the distribution of pseudorandom vectors generated by elliptic curves,Finite Fields Appl.93(2024), 102318. 29

work page 2024

[4] [4]

Hellekalek, General discrepancy estimates: the Walsh function system,Acta Arith.LXVII (3) (1994), 209–218

P. Hellekalek, General discrepancy estimates: the Walsh function system,Acta Arith.LXVII (3) (1994), 209–218

work page 1994

[5] [5]

Kohel, I

D. Kohel, I. Shparlinski, On exponential sums and group generators for elliptic curves over finite fields, Proc. the 4th Algorithmic Number Theory Symp., in: Lecture Notes in Comput. Sci., vol. 1838, Springer-Verlag, Berlin, 2000, pp. 395–404

work page 2000

[6] [6]

I. E. Shparlinski, Bilinear character sums over elliptic curves,Finite Fields Appl.14(2008), 132–141

work page 2008

[7] [7]

Ahmadi and I

O. Ahmadi and I. E. Shparlinski, Bilinear character sums and sum-product problems on elliptic curves,Proc. Edinburgh Math. Soc.53(2010), 1–12. 30

work page 2010