Small-Support Uncertainty Principles on $\mathbb{Z}/p$ over Finite Fields Article Swipe
Saad Quader
,
Alexander Russell
,
Ravi Sundaram
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1906.05179
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1906.05179
We establish an uncertainty principle for functions $f: \mathbb{Z}/p \rightarrow \mathbb{F}_q$ with constant support (where $p \mid q-1$). In particular, we show that for any constant $S > 0$, functions $f: \mathbb{Z}/p \rightarrow \mathbb{F}_q$ for which $|\text{supp}\; {f}| = S$ must satisfy $|\text{supp}\; \hat{f}| = (1 - o(1))p$. The proof relies on an application of Szemeredi's theorem; the celebrated improvements by Gowers translate into slightly stronger statements permitting conclusions for functions possessing slowly growing support as a function of $p$.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/1906.05179
- https://arxiv.org/pdf/1906.05179
- OA Status
- green
- References
- 12
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2952448214
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2952448214Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1906.05179Digital Object Identifier
- Title
-
Small-Support Uncertainty Principles on $\mathbb{Z}/p$ over Finite FieldsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2019Year of publication
- Publication date
-
2019-06-12Full publication date if available
- Authors
-
Saad Quader, Alexander Russell, Ravi SundaramList of authors in order
- Landing page
-
https://arxiv.org/abs/1906.05179Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1906.05179Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/1906.05179Direct OA link when available
- Concepts
-
Constant (computer programming), Function (biology), Combinatorics, Finite field, Mathematics, Physics, Discrete mathematics, Computer science, Biology, Evolutionary biology, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
12Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2952448214 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1906.05179 |
| ids.doi | https://doi.org/10.48550/arxiv.1906.05179 |
| ids.mag | 2952448214 |
| ids.openalex | https://openalex.org/W2952448214 |
| fwci | |
| type | preprint |
| title | Small-Support Uncertainty Principles on $\mathbb{Z}/p$ over Finite Fields |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11329 |
| topics[0].field.id | https://openalex.org/fields/26 |
| topics[0].field.display_name | Mathematics |
| topics[0].score | 0.9976999759674072 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2607 |
| topics[0].subfield.display_name | Discrete Mathematics and Combinatorics |
| topics[0].display_name | Limits and Structures in Graph Theory |
| topics[1].id | https://openalex.org/T11130 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.994700014591217 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Coding theory and cryptography |
| topics[2].id | https://openalex.org/T11166 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.9864000082015991 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2602 |
| topics[2].subfield.display_name | Algebra and Number Theory |
| topics[2].display_name | Analytic Number Theory Research |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2777027219 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6744260191917419 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1284190 |
| concepts[0].display_name | Constant (computer programming) |
| concepts[1].id | https://openalex.org/C14036430 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5897172689437866 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q3736076 |
| concepts[1].display_name | Function (biology) |
| concepts[2].id | https://openalex.org/C114614502 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5446691513061523 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[2].display_name | Combinatorics |
| concepts[3].id | https://openalex.org/C77926391 |
| concepts[3].level | 2 |
| concepts[3].score | 0.48376035690307617 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q603880 |
| concepts[3].display_name | Finite field |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.4727386236190796 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| concepts[5].id | https://openalex.org/C121332964 |
| concepts[5].level | 0 |
| concepts[5].score | 0.41445767879486084 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[5].display_name | Physics |
| concepts[6].id | https://openalex.org/C118615104 |
| concepts[6].level | 1 |
| concepts[6].score | 0.36699289083480835 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[6].display_name | Discrete mathematics |
| concepts[7].id | https://openalex.org/C41008148 |
| concepts[7].level | 0 |
| concepts[7].score | 0.17909550666809082 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[7].display_name | Computer science |
| concepts[8].id | https://openalex.org/C86803240 |
| concepts[8].level | 0 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[8].display_name | Biology |
| concepts[9].id | https://openalex.org/C78458016 |
| concepts[9].level | 1 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q840400 |
| concepts[9].display_name | Evolutionary biology |
| concepts[10].id | https://openalex.org/C199360897 |
| concepts[10].level | 1 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[10].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/constant |
| keywords[0].score | 0.6744260191917419 |
| keywords[0].display_name | Constant (computer programming) |
| keywords[1].id | https://openalex.org/keywords/function |
| keywords[1].score | 0.5897172689437866 |
| keywords[1].display_name | Function (biology) |
| keywords[2].id | https://openalex.org/keywords/combinatorics |
| keywords[2].score | 0.5446691513061523 |
| keywords[2].display_name | Combinatorics |
| keywords[3].id | https://openalex.org/keywords/finite-field |
| keywords[3].score | 0.48376035690307617 |
| keywords[3].display_name | Finite field |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.4727386236190796 |
| keywords[4].display_name | Mathematics |
| keywords[5].id | https://openalex.org/keywords/physics |
| keywords[5].score | 0.41445767879486084 |
| keywords[5].display_name | Physics |
| keywords[6].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[6].score | 0.36699289083480835 |
| keywords[6].display_name | Discrete mathematics |
| keywords[7].id | https://openalex.org/keywords/computer-science |
| keywords[7].score | 0.17909550666809082 |
| keywords[7].display_name | Computer science |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:1906.05179 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/1906.05179 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/1906.05179 |
| locations[1].id | doi:10.48550/arxiv.1906.05179 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.1906.05179 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5024321175 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Saad Quader |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Saad Quader |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5088846595 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-8228-6238 |
| authorships[1].author.display_name | Alexander Russell |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Alexander Russell |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5103159653 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5657-4298 |
| authorships[2].author.display_name | Ravi Sundaram |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Ravi Sundaram |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/1906.05179 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2019-06-27T00:00:00 |
| display_name | Small-Support Uncertainty Principles on $\mathbb{Z}/p$ over Finite Fields |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11329 |
| primary_topic.field.id | https://openalex.org/fields/26 |
| primary_topic.field.display_name | Mathematics |
| primary_topic.score | 0.9976999759674072 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2607 |
| primary_topic.subfield.display_name | Discrete Mathematics and Combinatorics |
| primary_topic.display_name | Limits and Structures in Graph Theory |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2980963558, https://openalex.org/W2893614166, https://openalex.org/W1882246857, https://openalex.org/W3103304230, https://openalex.org/W2185360082, https://openalex.org/W1992365905, https://openalex.org/W1976691234, https://openalex.org/W3212023493, https://openalex.org/W2964302506 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:1906.05179 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/1906.05179 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/1906.05179 |
| primary_location.id | pmh:oai:arXiv.org:1906.05179 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/1906.05179 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/1906.05179 |
| publication_date | 2019-06-12 |
| publication_year | 2019 |
| referenced_works | https://openalex.org/W2046521675, https://openalex.org/W2384675828, https://openalex.org/W1022649828, https://openalex.org/W2001007567, https://openalex.org/W2035816523, https://openalex.org/W2036595722, https://openalex.org/W1500453128, https://openalex.org/W1888174328, https://openalex.org/W2335400162, https://openalex.org/W2009505312, https://openalex.org/W1978920825, https://openalex.org/W2604113786 |
| referenced_works_count | 12 |
| abstract_inverted_index.- | 46 |
| abstract_inverted_index.= | 38, 44 |
| abstract_inverted_index.a | 76 |
| abstract_inverted_index.$S | 26 |
| abstract_inverted_index.$p | 15 |
| abstract_inverted_index.(1 | 45 |
| abstract_inverted_index.In | 18 |
| abstract_inverted_index.S$ | 39 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.an | 2, 52 |
| abstract_inverted_index.as | 75 |
| abstract_inverted_index.by | 60 |
| abstract_inverted_index.of | 54, 78 |
| abstract_inverted_index.on | 51 |
| abstract_inverted_index.we | 20 |
| abstract_inverted_index.$f: | 7, 30 |
| abstract_inverted_index.0$, | 28 |
| abstract_inverted_index.The | 48 |
| abstract_inverted_index.any | 24 |
| abstract_inverted_index.for | 5, 23, 34, 69 |
| abstract_inverted_index.the | 57 |
| abstract_inverted_index.$p$. | 79 |
| abstract_inverted_index.> | 27 |
| abstract_inverted_index.\mid | 16 |
| abstract_inverted_index.into | 63 |
| abstract_inverted_index.must | 40 |
| abstract_inverted_index.show | 21 |
| abstract_inverted_index.that | 22 |
| abstract_inverted_index.with | 11 |
| abstract_inverted_index.{f}| | 37 |
| abstract_inverted_index.proof | 49 |
| abstract_inverted_index.which | 35 |
| abstract_inverted_index.(where | 14 |
| abstract_inverted_index.Gowers | 61 |
| abstract_inverted_index.q-1$). | 17 |
| abstract_inverted_index.relies | 50 |
| abstract_inverted_index.slowly | 72 |
| abstract_inverted_index.growing | 73 |
| abstract_inverted_index.satisfy | 41 |
| abstract_inverted_index.support | 13, 74 |
| abstract_inverted_index.\hat{f}| | 43 |
| abstract_inverted_index.constant | 12, 25 |
| abstract_inverted_index.function | 77 |
| abstract_inverted_index.o(1))p$. | 47 |
| abstract_inverted_index.slightly | 64 |
| abstract_inverted_index.stronger | 65 |
| abstract_inverted_index.theorem; | 56 |
| abstract_inverted_index.establish | 1 |
| abstract_inverted_index.functions | 6, 29, 70 |
| abstract_inverted_index.principle | 4 |
| abstract_inverted_index.translate | 62 |
| abstract_inverted_index.celebrated | 58 |
| abstract_inverted_index.permitting | 67 |
| abstract_inverted_index.possessing | 71 |
| abstract_inverted_index.statements | 66 |
| abstract_inverted_index.Szemeredi's | 55 |
| abstract_inverted_index.\rightarrow | 9, 32 |
| abstract_inverted_index.application | 53 |
| abstract_inverted_index.conclusions | 68 |
| abstract_inverted_index.particular, | 19 |
| abstract_inverted_index.uncertainty | 3 |
| abstract_inverted_index.\mathbb{Z}/p | 8, 31 |
| abstract_inverted_index.improvements | 59 |
| abstract_inverted_index.\mathbb{F}_q$ | 10, 33 |
| abstract_inverted_index.$|\text{supp}\; | 36, 42 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |