pith. sign in

arxiv: 2510.11949 · v2 · submitted 2025-10-13 · 🧮 math.NA · cs.NA

Recovery of Integer Images from Minimal DFT Measurements: Uniqueness and Inversion Algorithms

Howard W Levinson , Isaac Viviano This is my paper

Pith reviewed 2026-05-18 06:59 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords integer image recoveryDFT measurementsuniquenessinversion algorithmsalgebraic reductiondynamic programminglattice reductionminimal sampling
0
0 comments X

The pith

Integer-valued images can be uniquely recovered from a minimal subset of their DFT coefficients by reducing the two-dimensional problem to several one-dimensional recoveries.

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

The paper shows that assuming an image has only integer pixel values turns an underdetermined DFT recovery problem into one with guaranteed uniqueness from a carefully chosen small set of measurements. Algebraic properties of the DFT are used to break the two-dimensional task into a series of one-dimensional recoveries, which in turn identify both the smallest number of coefficients needed and their exact locations. A reader might care because this prior knowledge of integrality replaces the usual requirement for a full set of DFT data with a minimal sampling pattern that still supports exact reconstruction. The authors further supply reconstruction algorithms that rely on dynamic programming to prune the search space and a lattice framework with the LLL algorithm to handle the remaining computational steps.

Core claim

Exact reconstruction of an image is possible from a limited subset of its Discrete Fourier Transform coefficients when the image is known to contain only integer values. The authors define an algebraic reduction from two-dimensional recovery to several well-chosen one-dimensional recoveries. This framework characterizes the minimum number and location of DFT coefficients required to guarantee unique reconstruction. Inversion algorithms then use dynamic programming for efficient recovery from the minimal measurements and a lattice-based approach with the LLL approximation algorithm to solve the associated NP-hard subproblems in practice.

What carries the argument

Algebraic reduction from two-dimensional to one-dimensional DFT recoveries, which determines the minimal set of coefficients that guarantees uniqueness for integer-valued images.

If this is right

  • Unique reconstruction is guaranteed for any integer image once the characterized minimal DFT coefficients are available.
  • The divide-and-conquer reduction reduces the search space enough to make dynamic programming practical for inversion.
  • Lattice reduction via the LLL algorithm renders the NP-hard subproblems computationally feasible for realistic image sizes.
  • The same framework supplies explicit procedures for both one-dimensional signals and two-dimensional images.

Where Pith is reading between the lines

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

  • Similar algebraic reductions might be developed for other discrete or quantized signals in signal processing tasks.
  • Measurement hardware in imaging systems could be redesigned to acquire only the minimal coefficient set when integrality is a safe prior.
  • Testing the algorithms on data with small rounding errors would clarify how far the exact-integer assumption can be relaxed.
  • Links to integer linear programming may suggest further speed-ups beyond the current dynamic programming and lattice steps.

Load-bearing premise

The image must consist of exact integer values and the DFT measurements must be precise with no noise or rounding.

What would settle it

Discovery of two distinct integer-valued images that produce identical values on the minimal DFT coefficient set identified by the reduction would disprove uniqueness.

Figures

Figures reproduced from arXiv: 2510.11949 by Howard W Levinson, Isaac Viviano.

Figure 1
Figure 1. Figure 1: Recursion tree showing subproblem structure when Algorithm [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: The Hasse diagram for the subgroup lattice of Z30. Two subgroups H ⊊ K are connected if they are related by inclusion and there is no subgroup H′ satisfying H ⊊ H′ ⊊ K. The lattice is arranged into levels where each subgroup on any given level is only connected to subgroups on the levels immediately above and below it. Right: In contrast with [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The Hasse diagram of the cyclic subgroup lattice of [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: For M = 1, 2, 3, the smoothed Monte Carlo distribution of guess errors ∥x − x∥2 (solid blue line), the experimental average error (blue dashed line, value in legend), and the theoretical bound (red dashed line, value in legend). The test set used 1e5 signals of length N = 30 with entries distributed as binom(N, 0.5) [PITH_FULL_IMAGE:figures/full_fig_p030_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: For M = 1, 2, 3, the estimated β2 from Eq. (5.30) plotted against β0 when N = 30 and K is computed from the bound in Eq. (5.35). We turn now to the choice of β0. Recall from Section 5.1 that, although setting β0 > K ensures |γ| ≤ 1, larger β0 values lengthen the shortest lattice vector. An intermediate value of β0 smaller than K will balance these effects [PITH_FULL_IMAGE:figures/full_fig_p030_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Left: plot of the totient function ϕ(N) vs N. Center: For number of DFT coefficients M = 1, 2, 3, plots of the estimated β2 from Eq. (5.30) vs N with L = 1. Right: For binomial trial parameter L = N0 , N1 , N2 , plots of the estimated β2 from Eq. (5.30) vs N with M = 1. In the estimate for K from Eq. (5.35), the binomial probability parameter is fixed at p = 0.5. Finally, [PITH_FULL_IMAGE:figures/full_fig… view at source ↗
Figure 7
Figure 7. Figure 7: Left: For N = 29 through 33, plots of the estimated β2 from Eq. (5.30) vs M for 1 ≤ M < ϕ(N)/2. Right: For N = 11 and M = 1 through 5, plots of ρ(β2, γ) from Eq. (5.29) vs |γ| where β2 is given by Eq. (5.30). 6. Numerical Reconstructions 6.1. Floating Point LLL for Integer Lattices As mentioned in Section 4.4, our implementations of Algorithms 2 and 4 use an approximation algorithm to address the NP-hard s… view at source ↗
Figure 8
Figure 8. Figure 8: For M = 1, 2, and 3: Fraction of test signals correctly recovered over a range of β2 values (blue solid line) compared to heuristic β2 value (red dashed line). The test set used 1000 random signals of length N = 23 with entries distributed as binom(N, 0.5). 34 [PITH_FULL_IMAGE:figures/full_fig_p034_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: For N = 47 and 48 with M = 1: fraction of test signals recovered correctly (green), fraction where LLL found shorter basis vector than desired (orange), and fraction where either LLL succeeded or found a shorter vector (blue) compared to theoretical estimated β2 value (red dashed line). For each N, the test set used 300 random signal of length N with entries distributed as binom(N, 0.5). The verification t… view at source ↗
Figure 10
Figure 10. Figure 10: For M = 1, 2, and 3, plots of β2 values dependence on L. For several values of L, the associated test set consisted of 100 random signals of length N = 31 with entries distributed as binom(L, 0.5). The theoretical estimate of β2 (blue line), 50th percentile (orange line), 90th percentile (green line), and 100th percentile (red line) are all plotted. inversion and β2 = 1e14 for double precision inversion. … view at source ↗
Figure 11
Figure 11. Figure 11: For N = 30 and M = 1 with single precision: Frac￾tion of test signals correctly recovered over a range of β2 values (blue solid line) compared to heuristic β2 value (red dashed line). The test set used 1000 random signals of length N with entries distributed as binom(N, 0.5) [PITH_FULL_IMAGE:figures/full_fig_p039_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Using a 45×45 QR code containing the message “Hello World!” as a model image, Left: the zero-filled reconstruction from a minimal set of sampled DFT coefficients; Right: the reconstruction by Algorithm 4 from the minimal spectrum (coincides exactly with model). 42 [PITH_FULL_IMAGE:figures/full_fig_p042_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: For three models, the left column has the zero-filled reconstruction from a minimal set of sampled DFT coefficients; [PITH_FULL_IMAGE:figures/full_fig_p044_13.png] view at source ↗
read the original abstract

Exact reconstruction of an image from measurements of its Discrete Fourier Transform (DFT) typically requires all DFT coefficients to be available. However, incorporating the prior assumption that the image contains only integer values enables unique recovery from a limited subset of DFT coefficients. This paper develops both theoretical and algorithmic foundations for this problem. We use algebraic properties of the DFT to define a reduction from two-dimensional recovery to several well-chosen one-dimensional recoveries. Our reduction framework characterizes the minimum number and location of DFT coefficients that must be sampled to guarantee unique reconstruction of an integer-valued image. Algorithmically, we develop reconstruction procedures which use dynamic programming to efficiently recover an integer signal or image from its minimal set of DFT measurements. While the new inversion algorithms still involve NP-hard subproblems, we demonstrate how the divide-and-conquer approach drastically reduces the associated search space. To solve the NP-hard subproblems, we employ a lattice-based framework which leverages the LLL approximation algorithm to make the algorithms fast and practical.

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.

Referee Report

2 major / 2 minor

Summary. The paper claims that the integer-valued prior on images enables unique recovery from a minimal subset of DFT coefficients. It develops an algebraic reduction from 2D to multiple 1D recovery problems to characterize the minimal number and locations of required DFT samples, and proposes dynamic programming combined with lattice reduction (LLL) algorithms to solve the resulting NP-hard integer subproblems efficiently.

Significance. If the uniqueness results via the reduction and the correctness of the LLL-based recovery hold, this would be a significant contribution to compressive sensing and inverse problems in numerical analysis, allowing reconstruction of integer images with substantially fewer DFT measurements than standard methods. The divide-and-conquer reduction of search space is a notable strength.

major comments (2)
  1. [Reduction Framework] Reduction framework: The central claim that the algebraic reduction from 2D to 1D characterizes the minimum number and location of DFT coefficients for guaranteed uniqueness lacks an explicit theorem or set of conditions in the provided description. This is load-bearing for the theoretical contribution and requires a precise statement of the uniqueness result.
  2. [Inversion Algorithms] Lattice-based framework for NP-hard subproblems: The manuscript employs LLL to approximate the shortest vector and relies on a post-approximation verification step to recover the exact integer solution. However, LLL only guarantees a 2^{O(d)} approximation factor; without a proof that verification always discards spurious lattice vectors that satisfy the sampled DFT equations to machine precision but differ from the true image, the correctness of the inversion algorithms is not established.
minor comments (2)
  1. The abstract states that the divide-and-conquer approach 'drastically reduces the associated search space' but provides no quantitative bounds or small-scale examples to illustrate the reduction in complexity.
  2. Consider adding a short discussion of related work on DFT uniqueness for discrete signals or lattice methods in signal recovery to better situate the contribution.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and constructive feedback on our manuscript. The comments highlight important aspects that will strengthen the presentation of our results. We address each major comment below and plan to incorporate revisions as indicated.

read point-by-point responses

  1. Referee: Reduction framework: The central claim that the algebraic reduction from 2D to 1D characterizes the minimum number and location of DFT coefficients for guaranteed uniqueness lacks an explicit theorem or set of conditions in the provided description. This is load-bearing for the theoretical contribution and requires a precise statement of the uniqueness result.

    Authors: We agree that making the uniqueness result explicit is crucial. Although the manuscript describes the algebraic reduction and its implications for the minimal DFT samples, we will add a formal theorem in the revised version. The theorem will state the precise conditions on the DFT coefficient locations and the integer image properties that ensure the reduction leads to unique recovery. This will include the characterization of the minimum number of measurements required. revision: yes

  2. Referee: Lattice-based framework for NP-hard subproblems: The manuscript employs LLL to approximate the shortest vector and relies on a post-approximation verification step to recover the exact integer solution. However, LLL only guarantees a 2^{O(d)} approximation factor; without a proof that verification always discards spurious lattice vectors that satisfy the sampled DFT equations to machine precision but differ from the true image, the correctness of the inversion algorithms is not established.

    Authors: We appreciate this observation on the theoretical guarantees. The LLL algorithm is used to find a good approximation to the shortest vector in the lattice defined by the DFT constraints, and the verification checks exact satisfaction of the measurements. Due to the uniqueness guaranteed by our reduction framework, any integer solution satisfying the minimal DFT equations must coincide with the original image. In the revision, we will add a clarification that the verification step, combined with the uniqueness, ensures correctness, and discuss how the reduced problem dimensions mitigate the approximation factor issues in practice. revision: yes

Circularity Check

0 steps flagged

No circularity: algebraic DFT reduction and integer prior are independent inputs

full rationale

The derivation chain reduces 2D recovery to 1D via algebraic DFT properties (standard Fourier analysis, not self-defined) and characterizes minimal samples from the integer-valued assumption, which is stated upfront as the enabling prior rather than derived from the method. No fitted parameters are renamed as predictions, no self-citations are load-bearing for uniqueness or uniqueness theorems, and no ansatz is imported via prior work. The DP and LLL steps are practical solvers for the resulting NP-hard subproblems but do not feed back into the theoretical uniqueness claim. The framework is self-contained against external DFT algebra and integer lattice benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard algebraic properties of the DFT and the modeling choice that pixel values are exactly integers; no free parameters, invented entities, or ad-hoc axioms are described in the abstract.

axioms (1)
  • domain assumption Algebraic properties of the DFT permit a reduction from two-dimensional integer image recovery to several one-dimensional recoveries.
    Invoked to characterize the minimum number and location of DFT coefficients needed for uniqueness.

pith-pipeline@v0.9.0 · 5697 in / 1311 out tokens · 35878 ms · 2026-05-18T06:59:25.982272+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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

67 extracted references · 67 canonical work pages · 2 internal anchors

  1. [1]

    E. J. Candes, J. K. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measure- ments, Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59 (2006) 1207–1223

    work page 2006

  2. [2]

    D. L. Donoho, Compressed sensing, IEEE Transactions on information theory 52 (2006) 1289–1306

    work page 2006

  3. [3]

    M. F. Duarte, Y. C. Eldar, Structured compressed sensing: From theory to applications, IEEE Trans- actions on signal processing 59 (2011) 4053–4085

    work page 2011

  4. [4]

    A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-optimal sparse fourier repre- sentations via sampling, in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002, pp. 152–161. 46

    work page 2002

  5. [5]

    A. C. Gilbert, S. Muthukrishnan, M. Strauss, Improved time bounds for near-optimal sparse fourier representations, in: Wavelets xi, volume 5914, SPIE, 2005, pp. 398–412

    work page 2005

  6. [6]

    Rudelson, R

    M. Rudelson, R. Vershynin, On sparse reconstruction from fourier and gaussian measurements, Commu- nications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 61 (2008) 1025–1045

    work page 2008

  7. [7]

    Rudelson, R

    M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and gaussian mea- surements, in: 2006 40th Annual Conference on Information Sciences and Systems, IEEE, 2006, pp. 207–212

    work page 2006

  8. [8]

    Candes, J

    E. Candes, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incompletefrequencyinformation, IEEETransactionsonInformationTheory52(2006)489–509.doi:10. 1109/TIT.2005.862083

    work page arXiv 2006

  9. [9]

    Plonka, K

    G. Plonka, K. Wannenwetsch, A deterministic sparse fft algorithm for vectors with small support, Numerical Algorithms 71 (2016) 889–905

    work page 2016

  10. [10]

    Rajaby, S

    E. Rajaby, S. M. Sayedi, A structured review of sparse fast fourier transform algorithms, Digital Signal Processing 123 (2022) 103403

    work page 2022

  11. [11]

    Bittens, R

    S. Bittens, R. Zhang, M. A. Iwen, A deterministic sparse fft for functions with structured fourier sparsity, Advances in Computational Mathematics 45 (2019) 519–561

    work page 2019

  12. [12]

    Hsieh, C.-S

    S.-H. Hsieh, C.-S. Lu, S.-C. Pei, Sparse fast fourier transform by downsampling, in: 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, 2013, pp. 5637–5641

    work page 2013

  13. [13]

    A. C. Gilbert, P. Indyk, M. Iwen, L. Schmidt, Recent developments in the sparse fourier transform: A compressed fourier transform for big data, IEEE Signal Processing Magazine 31 (2014) 91–100

    work page 2014

  14. [14]

    G. T. Herman, A. Kuba, Discrete tomography: Foundations, algorithms, and applications, Springer Science & Business Media, 2012

    work page 2012

  15. [15]

    P. T. Boufounos, R. G. Baraniuk, 1-bit compressive sensing, in: 2008 42nd Annual Conference on Information Sciences and Systems, IEEE, 2008, pp. 16–21

    work page 2008

  16. [16]

    R. G. Parker, R. L. Rardin, Discrete optimization, Elsevier, 2014

    work page 2014

  17. [17]

    Alpers, P

    A. Alpers, P. Gritzmann, L. Thorens, Stability and instability in discrete tomography, in: Digital and Image Geometry: Advanced Lectures, Springer, 2002, pp. 175–186

    work page 2002

  18. [18]

    R. M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45–68

    work page 1975

  19. [19]

    P. Q. Nguyen, B. Vallée, The LLL algorithm, Springer, 2010

    work page 2010

  20. [20]

    Joseph, V

    G. Joseph, V. Gandikota, A. Bhandari, J. Choi, I.-s. Kim, G. Lee, M. Matthaiou, C. R. Murthy, H. Q. Ngo, P. K. Varshney, et al., Low-resolution compressed sensing and beyond for communications and sensing: Trends and opportunities, Signal Processing 235 (2025) 110020

    work page 2025

  21. [21]

    J. Zhan, B. Nazer, U. Erez, M. Gastpar, Integer-forcing linear receivers, IEEE Transactions on Infor- mation Theory 60 (2014) 7661–7685

    work page 2014

  22. [22]

    G. T. Herman, A. Kuba, Discrete tomography in medical imaging, Proceedings of the IEEE 91 (2003) 1612–1626

    work page 2003

  23. [23]

    A. Kadu, T. van Leeuwen, A convex formulation for binary tomography, IEEE Transactions on Com- putational Imaging 6 (2019) 1–11. 47

    work page 2019

  24. [24]

    K. J. Batenburg, J. Sijbers, Dart: a practical reconstruction algorithm for discrete tomography, IEEE Transactions on Image Processing 20 (2011) 2542–2553

    work page 2011

  25. [25]

    Coronado, G

    K.J.Batenburg, S.Bals, J.Sijbers, C.Kübel, P.A.Midgley, J.Hernandez, U.Kaiser, E.R.Encina, E.A. Coronado, G. Van Tendeloo, 3d imaging of nanomaterials by discrete tomography, Ultramicroscopy 109 (2009) 730–740

    work page 2009

  26. [26]

    A. E. Yagle, A convergent composite mapping fourier domain iterative algorithm for 3-d discrete tomog- raphy, Linear Algebra and its Applications 339 (2001) 91–109. URL: https://www.sciencedirect.com/ science/article/pii/S002437950100458X. doi:https://doi.org/10.1016/S0024-3795(01)00458-X

    work page doi:10.1016/s0024-3795(01)00458-x 2001

  27. [27]

    Esedoglu, Blind deconvolution of bar code signals, Inverse Problems 20 (2003) 121

    S. Esedoglu, Blind deconvolution of bar code signals, Inverse Problems 20 (2003) 121

    work page 2003

  28. [28]

    Di Zenzo, L

    S. Di Zenzo, L. Cinque, S. Levialdi, Run-based algorithms for binary image analysis and processing, IEEE Transactions on Pattern Analysis and Machine Intelligence 18 (1996) 83–89. doi:10.1109/34. 476016

    work page doi:10.1109/34 1996

  29. [29]

    M. Ren, J. Yang, H. Sun, Tracing boundary contours in a binary image, Image and Vision Comput- ing 20 (2002) 125–131. URL: https://www.sciencedirect.com/science/article/pii/S0262885601000919. doi:https://doi.org/10.1016/S0262-8856(01)00091-9

    work page doi:10.1016/s0262-8856(01)00091-9 2002

  30. [30]

    Marchand-Maillet, Y

    S. Marchand-Maillet, Y. M. Sharaiha, Binary Digital Image Processing, Elsevier, 2000. URL: http: //dx.doi.org/10.1016/B978-0-12-470505-0.X5000-X. doi:10.1016/b978-0-12-470505-0.x5000-x

    work page doi:10.1016/b978-0-12-470505-0.x5000-x 2000

  31. [31]

    Pei, K.-W

    S.-C. Pei, K.-W. Chang, Binary signal perfect recovery from partial dft coefficients, IEEE Transactions on Signal Processing 70 (2022) 3848–3861. doi:10.1109/TSP.2022.3190615

    work page doi:10.1109/tsp.2022.3190615 2022

  32. [32]

    H. W. Levinson, V. A. Markel, Binary discrete fourier transform and its inversion, IEEE Transactions on Signal Processing 69 (2021) 3484–3499. doi:10.1109/TSP.2021.3088215

    work page doi:10.1109/tsp.2021.3088215 2021

  33. [33]

    H. W. Levinson, V. Markel, N. Triantafillou, Inversion of band-limited discrete fourier transforms of binary images: Uniqueness and algorithms, SIAM Journal on Imaging Sciences 16 (2023) 1338–1369

    work page 2023

  34. [34]

    K. M. Nashold, B. E. Saleh, Synthesis of two-dimensional binary images through band-limited systems: a slicing method, IEEE Transactions on Acoustics, Speech, and Signal Processing 37 (2002) 1271–1279

    work page 2002

  35. [35]

    K. M. Nashold, J. A. Bucklew, W. Rudin, B. E. Saleh, Synthesis of binary images from band-limited functions, Journal of the Optical Society of America A 6 (1989) 852–858

    work page 1989

  36. [36]

    Mao, Reconstruction of binary functions and shapes from incomplete frequency information, IEEE Transactions on Information Theory 58 (2012) 3642–3653

    Y. Mao, Reconstruction of binary functions and shapes from incomplete frequency information, IEEE Transactions on Information Theory 58 (2012) 3642–3653

    work page 2012

  37. [37]

    Vetterli, P

    M. Vetterli, P. Marziliano, T. Blu, Sampling signals with finite rate of innovation, IEEE transactions on Signal Processing 50 (2002) 1417–1428

    work page 2002

  38. [38]

    Stolk, K

    A. Stolk, K. J. Batenburg, An algebraic framework for discrete tomography: Revealing the structure of dependencies, SIAM Journal on Discrete Mathematics 24 (2010) 1056–1079

    work page 2010

  39. [39]

    J.A.Tropp, Onthelinearindependenceofspikesandsines, JournalofFourierAnalysisandApplications 14 (2008) 838–858

    work page 2008

  40. [40]

    Tao, An uncertainty principle for cyclic groups of prime order, Math

    T. Tao, An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12 (2005) 121–127

    work page 2005

  41. [41]

    A. K. Lenstra, H. W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math- ematische Annalen 261 (1982) 515–534. URL: http://dx.doi.org/10.1007/BF01457454. doi:10.1007/ bf01457454. 48

    work page doi:10.1007/bf01457454 1982

  42. [42]

    Coppersmith, Finding a small root of a univariate modular equation, in: U

    D. Coppersmith, Finding a small root of a univariate modular equation, in: U. Maurer (Ed.), Advances in Cryptology — EUROCRYPT ’96, Springer Berlin Heidelberg, Berlin, Heidelberg, 1996, pp. 155–165

    work page 1996

  43. [43]

    H. W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research 8 (1983) 538–548. URL: http://www.jstor.org/stable/3689168

    work page arXiv 1983

  44. [44]

    Hastad, B

    J. Hastad, B. Just, J. C. Lagarias, C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM Journal on Computing 18 (1989) 859–881. URL: https://doi.org/10.1137/ 0218059. doi:10.1137/0218059.arXiv:https://doi.org/10.1137/0218059

    work page doi:10.1137/0218059.arxiv:https://doi.org/10.1137/0218059 1989

  45. [45]

    D. H. Bailey, J. M. Borwein, PSLQ: An Algorithm to Discover Integer Relations, Technical Report, Ernest Orlando Lawrence Berkeley National Laboratory, Berkeley, CA (US), 2009. URL: https://www. osti.gov/biblio/963658. doi:10.2172/963658

    work page doi:10.2172/963658 2009

  46. [46]

    Aardal, C

    K. Aardal, C. A. J. Hurkens, A. K. Lenstra, Solving a system of linear diophantine equations with lower and upper bounds on the variables, Mathematics of Operations Research 25 (2000) 427–442. URL: http://www.jstor.org/stable/3690477

    work page arXiv 2000

  47. [47]

    Pei, K.-W

    S.-C. Pei, K.-W. Chang, Binary image fast perfect recovery from sparse 2d-dft coefficients, in: ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2023, pp. 1–5

    work page 2023

  48. [48]

    Representing and counting the subgroups of the group Z_m x Z_n

    M. Hampejs, N. Holighaus, L. Tóth, C. Wiesmeyr, Representing and counting the subgroups of the groupz m ×z n, 2014. URL: https://arxiv.org/abs/1211.1797.arXiv:1211.1797

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  49. [49]

    Myerson, How small can a sum of roots of unity be?, The American Mathematical Monthly 93 (1986) 457–459

    G. Myerson, How small can a sum of roots of unity be?, The American Mathematical Monthly 93 (1986) 457–459

    work page 1986

  50. [50]

    Barber, Small sums of five roots of unity, Bulletin of the London Mathematical Society 55 (2023) 1890–1906

    B. Barber, Small sums of five roots of unity, Bulletin of the London Mathematical Society 55 (2023) 1890–1906

    work page 2023

  51. [51]

    Buhler, M

    J. Buhler, M. Shokrollahi, V. Stemann, Fast and precise fourier transforms, IEEE Transactions on Information Theory 46 (2000) 213–228. doi:10.1109/18.817519

    work page doi:10.1109/18.817519 2000

  52. [52]

    J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex fourier series, Mathe- matics of Computation 19 (1965) 297–301. URL: http://www.jstor.org/stable/2003354

    work page arXiv 1965

  53. [53]

    Marchand, A

    H. Marchand, A. Martin, R. Weismantel, L. Wolsey, Cutting planes in integer and mixed integer pro- gramming, Discrete Applied Mathematics 123 (2002) 397–446. URL: https://www.sciencedirect.com/ science/article/pii/S0166218X01003481. doi:https://doi.org/10.1016/S0166-218X(01)00348-1

    work page doi:10.1016/s0166-218x(01)00348-1 2002

  54. [54]

    J. C. Lagarias, A. M. Odlyzko, Solving low-density subset sum problems, J. ACM 32 (1985) 229–246. URL: https://doi.org/10.1145/2455.2461. doi:10.1145/2455.2461

    work page doi:10.1145/2455.2461 1985

  55. [55]

    J. A. Greenwood, D. Durand, The distribution of length and components of the sum of n random unit vectors, The Annals of Mathematical Statistics (1955) 233–246

    work page 1955

  56. [56]

    Probability density function of the Cartesian x-coordinate of the random point inside the hypersphere

    A. Kuketayev, Probability density function of the cartesian x-coordinate of the random point inside the hypersphere, arXiv preprint arXiv:1306.0290 (2013)

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  57. [57]

    Caiado, P

    C. Caiado, P. Rathie, Polynomial coefficients and distribution of the sum of discrete uniform variables, in: M. A. M., P. M. A., J. K. K., J. Joy (Eds.), Eighth Annual Conference of the Society of Special Func- tions and their Applications, 2007. URL: https://durham-repository.worktribe.com/output/1158118, ePrint Processing Status: DRO Team waiting for pe...

    work page arXiv 2007

  58. [58]

    Kalbach, T

    A. Kalbach, T. Chinburg, Lll algorithm for lattice basis reduction, 2024. URL: https://arxiv.org/abs/ 2410.22196.arXiv:2410.22196. 49

    work page arXiv 2024

  59. [59]

    C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, T. E. Oliphant, Array programming wi...

    work page doi:10.1038/s41586-020-2649-2 2020

  60. [60]

    P. Q. Nguyen, D. Stehlé, An lll algorithm with quadratic complexity, SIAM Journal on Computing 39 (2009) 874–903

    work page 2009

  61. [61]

    Stehlé, Floating-point lll: theoretical and practical aspects, in: The LLL Algorithm: survey and applications, Springer, 2009, pp

    D. Stehlé, Floating-point lll: theoretical and practical aspects, in: The LLL Algorithm: survey and applications, Springer, 2009, pp. 179–213

    work page 2009

  62. [62]

    T. F. development team, fplll, a lattice reduction library, Version: 5.5.0, 2023. URL: https://github. com/fplll/fplll, available at https://github.com/fplll/fplll

    work page 2023

  63. [63]

    T. F. development team, fpylll, a Python wrapper for the fplll lattice reduction library, Version: 0.6.4,

    work page

  64. [64]

    URL: https://github.com/fplll/fpylll, available at https://github.com/fplll/fpylll

    work page

  65. [65]

    Viviano, intvert, a Python package for inversion of integer arrays from partial DFT samples, 2025

    I. Viviano, intvert, a Python package for inversion of integer arrays from partial DFT samples, 2025. URL: https://pypi.org/project/intvert/, available at https://pypi.org/project/intvert/

    work page 2025

  66. [66]

    Tiwari, An introduction to qr code technology, in: 2016 International Conference on Information Technology (ICIT), 2016, pp

    S. Tiwari, An introduction to qr code technology, in: 2016 International Conference on Information Technology (ICIT), 2016, pp. 39–44. doi:10.1109/ICIT.2016.021

    work page doi:10.1109/icit.2016.021 2016

  67. [67]

    W. F. Schreiber, Image processing for quality improvement, Proceedings of the IEEE 66 (2005) 1640– 1651. 50

    work page 2005