On sets of large Fourier transform under changes in domain

DOI10.1016/J.ACHA.2017.08.002MaRDI QIDQ1748260zbMATH OpenOpenAlexFDO

Authors Joel Laity, Barak Shani

Publication date 9 May 2018

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04330

Mathematics Subject Classification ID

Trigonometric series of special types (positive coefficients, monotonic coefficients, etc.) (42A32) Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25)

Abstract: A function $f:mathbb{Z}_{n}omathbbC$ can be represented as a linear combination $f(x)=su{m}_{alphainmathbb{Z}_n}widehatf(alpha)ch{i}_{alpha,n}(x)$ where $widehatf$ is the (discrete) Fourier transform of $f$. Clearly, the basis $ch{i}_{alpha,n}(x):=exp(2piialphax/n)$ depends on the value $n$. We show that if $f$ has "large" Fourier coefficients, then the function $widetildef:mathbb{Z}_{m}omathbbC$, given by [ widetilde{f}(x) = �egin{cases} f(x) & ext{when } 0leq x < min(n, m), 0 & ext{otherwise}, end{cases} ] also has "large" coefficients. Moreover, they are all contained in a "small" interval around $lfloorfracmnalphaceil$ for each $alphainmathbb{Z}_n$ such that $widehatf(alpha)$ is large. One can use this result to recover the large Fourier coefficients of a function $f$ by redefining it on a convenient domain. One can also use this result to reprove a result by Morillo and R{`a}fols: emph{single-bit} functions, defined over any domain, have a small set of large coefficients.

Recommendations

• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• On the Fourier-Walsh coefficients
• On the Fourier coefficients of functions concentrated on a subset of the circle
• Finite Fourier transform for functions with restricted support
• Highly nonlinear functions

Cites work

• scientific article; zbMATH DE number 2159066 (Why is no real title available?)
• On sets of large exponential sums
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The Security of All Bits Using List Decoding

Cited in

(3)

• The security of all private-key bits in isogeny-based schemes
• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• Large sets without Fourier restriction theorems

This page was built for publication: On sets of large Fourier transform under changes in domain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748260)