{"id":548715,"date":"2018-11-07T13:43:21","date_gmt":"2018-11-07T21:43:21","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/?post_type=msr-research-item&p=548715"},"modified":"2018-11-07T14:57:36","modified_gmt":"2018-11-07T22:57:36","slug":"gaussian-width-bounds-with-applications-to-arithmetic-progressions-in-random-settings","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/gaussian-width-bounds-with-applications-to-arithmetic-progressions-in-random-settings\/","title":{"rendered":"Gaussian width bounds with applications to arithmetic progressions in random settings"},"content":{"rendered":"

Motivated by problems on random differences in Szemer\u00e9di’s theorem and on
\nlarge deviations for arithmetic progressions in random sets, we prove upper
\nbounds on the Gaussian width of point sets that are formed by the image of the
\n$n$-dimensional Boolean hypercube under a mapping
\n$\u03c8:\\mathbb{R}^n\\to\\mathbb{R}^k$, where each coordinate is a constant-degree
\nmultilinear polynomial with 0-1 coefficients. We show the following
\napplications of our bounds. Let $[\\mathbb{Z}\/N\\mathbb{Z}]_p$ be the random
\nsubset of $\\mathbb{Z}\/N\\mathbb{Z}$ containing each element independently with
\nprobability $p$.<\/p>\n

$\\bullet$ A set $D\\subseteq \\mathbb{Z}\/N\\mathbb{Z}$ is $\\ell$-intersective if
\nany dense subset of $\\mathbb{Z}\/N\\mathbb{Z}$ contains a proper $(\\ell+1)$-term
\narithmetic progression with common difference in $D$. Our main result implies
\nthat $[\\mathbb{Z}\/N\\mathbb{Z}]_p$ is $\\ell$-intersective with probability $1 –
\no(1)$ provided $p \\geq \u03c9(N^{-\u03b2_\\ell}\\log N)$ for $\u03b2_\\ell =
\n(\\lceil(\\ell+1)\/2\\rceil)^{-1}$. This gives a polynomial improvement for all
\n$\\ell \\ge 3$ of a previous bound due to Frantzikinakis, Lesigne and Wierdl, and
\nreproves more directly the same improvement shown recently by the authors and
\nDvir.<\/p>\n

$\\bullet$ Let $X_k$ be the number of $k$-term arithmetic progressions in
\n$[\\mathbb{Z}\/N\\mathbb{Z}]_p$ and consider the large deviation rate
\n$\u03c1_k(\u03b4) = \\log\\Pr[X_k \\geq (1+\u03b4)\\mathbb{E}X_k]$. We give quadratic
\nimprovements of the best-known range of $p$ for which a highly precise estimate
\nof $\u03c1_k(\u03b4)$ due to Bhattacharya, Ganguly, Shao and Zhao is valid for
\nall odd $k \\geq 5$.<\/p>\n

We also discuss connections with error correcting codes (locally decodable
\ncodes) and the Banach-space notion of type for injective tensor products of
\n$\\ell_p$-spaces.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

Motivated by problems on random differences in Szemer\u00e9di’s theorem and on large deviations for arithmetic progressions in random sets, we prove upper bounds on the Gaussian width of point sets that are formed by the image of the $n$-dimensional Boolean hypercube under a mapping $\u03c8:\\mathbb{R}^n\\to\\mathbb{R}^k$, where each coordinate is a constant-degree multilinear polynomial with 0-1 […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"International Mathematics Research Notices (IMRN)","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2018-10-1","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":false,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13546],"msr-publication-type":[193715],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-548715","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-computational-sciences-mathematics","msr-locale-en_us"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2018-10-1","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"International Mathematics Research Notices (IMRN)","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":0,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"doi","viewUrl":"false","id":"false","title":"10.1093\/imrn\/rny238","label_id":"243109","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/arxiv.org\/abs\/1711.05624","label_id":"243103","label":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Jop Briet","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Sivakanth Gopi","user_id":37830,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Sivakanth Gopi"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"article","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/548715","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/548715\/revisions"}],"predecessor-version":[{"id":548739,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/548715\/revisions\/548739"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=548715"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=548715"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=548715"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=548715"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=548715"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=548715"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=548715"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=548715"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=548715"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=548715"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=548715"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=548715"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=548715"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}