{
  "id": "1610.04330",
  "version": "v1",
  "published": "2016-10-14T04:44:49.000Z",
  "updated": "2016-10-14T04:44:49.000Z",
  "title": "On Sets of Large Fourier Transform Under Changes in Domain",
  "authors": [
    "Joel Laity",
    "Barak Shani"
  ],
  "categories": [
    "math.CA"
  ],
  "abstract": "A function $f:\\mathbb{Z}_n \\to \\mathbb{C}$ can be represented as a linear combination $f(x)=\\sum_{\\alpha \\in \\mathbb{Z}_n}\\widehat{f}(\\alpha) \\chi_{\\alpha,n}(x)$ where $\\widehat{f}$ is the (discrete) Fourier transform of $f$. Clearly, the basis $\\{\\chi_{\\alpha,n}(x):=\\exp(2\\pi i \\alpha x/n)\\}$ depends on the value $n$. We show that if $f$ has \"large\" Fourier coefficients, then the function $\\widetilde{f}:\\mathbb{Z}_m \\to \\mathbb{C}$, given by \\[ \\widetilde{f}(x) = \\begin{cases} f(x) & \\text{when } 0\\leq x < \\min(n, m), \\newline 0 & \\text{otherwise}, \\end{cases} \\] also has \"large\" coefficients. Moreover, they are all contained in a \"small\" interval around $\\lfloor \\frac{m}{n}\\alpha \\rceil$ for each $\\alpha \\in \\mathbb{Z}_n$ such that $\\widehat{f}(\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-14T04:44:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large fourier transform",
      "large fourier coefficients",
      "linear combination",
      "small set",
      "convenient domain"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}