SUMSETS IN THE HYPERCUBE

Noga Alon; O. R. Zamir

doi:10.1137/24M165569X

SUMSETS IN THE HYPERCUBE

Noga Alon, O. R. Zamir

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A subset S of the Boolean hypercube \BbbFⁿ₂ is a sumset if S = A + A = \{a + b | a, b \in A\} for some A \subseteq \BbbFⁿ₂ . We prove that the number of sumsets in \BbbFⁿ₂ is asymptotically (2ⁿ - 1)2^2n-1 . Furthermore, we show that the family of sumsets in \BbbFⁿ₂ is almost identical to the family of all subsets of \BbbFⁿ₂ that contain a complete linear subspace of codimension 1.

Original language	English (US)
Pages (from-to)	314-326
Number of pages	13
Journal	SIAM Journal on Discrete Mathematics
Volume	39
Issue number	1
DOIs	https://doi.org/10.1137/24M165569X
State	Published - 2025

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

additive combinatorics
combinatorics
sumsets

Access to Document

10.1137/24M165569X

Cite this

@article{f8bca70087db41f6ad2467ccf189cf3c,

title = "SUMSETS IN THE HYPERCUBE",

abstract = "A subset S of the Boolean hypercube \BbbFn2 is a sumset if S = A + A = \{a + b | a, b \in A\} for some A \subseteq \BbbFn2 . We prove that the number of sumsets in \BbbFn2 is asymptotically (2n - 1)22n-1 . Furthermore, we show that the family of sumsets in \BbbFn2 is almost identical to the family of all subsets of \BbbFn2 that contain a complete linear subspace of codimension 1.",

keywords = "additive combinatorics, combinatorics, sumsets",

author = "Noga Alon and Zamir, {O. R.}",

note = "Publisher Copyright: 314 Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited. functions f and g denotes that f = (1 + o(1))g, where the o(1)-term tends to 0 as the parameters of the functions grow to infinity. Equivalently, this means that the limit of the ratio f/g as the parameters grow is 1.",

year = "2025",

doi = "10.1137/24M165569X",

language = "English (US)",

volume = "39",

pages = "314--326",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - SUMSETS IN THE HYPERCUBE

AU - Alon, Noga

AU - Zamir, O. R.

N1 - Publisher Copyright: 314 Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. functions f and g denotes that f = (1 + o(1))g, where the o(1)-term tends to 0 as the parameters of the functions grow to infinity. Equivalently, this means that the limit of the ratio f/g as the parameters grow is 1.

PY - 2025

Y1 - 2025

N2 - A subset S of the Boolean hypercube \BbbFn2 is a sumset if S = A + A = \{a + b | a, b \in A\} for some A \subseteq \BbbFn2 . We prove that the number of sumsets in \BbbFn2 is asymptotically (2n - 1)22n-1 . Furthermore, we show that the family of sumsets in \BbbFn2 is almost identical to the family of all subsets of \BbbFn2 that contain a complete linear subspace of codimension 1.

AB - A subset S of the Boolean hypercube \BbbFn2 is a sumset if S = A + A = \{a + b | a, b \in A\} for some A \subseteq \BbbFn2 . We prove that the number of sumsets in \BbbFn2 is asymptotically (2n - 1)22n-1 . Furthermore, we show that the family of sumsets in \BbbFn2 is almost identical to the family of all subsets of \BbbFn2 that contain a complete linear subspace of codimension 1.

KW - additive combinatorics

KW - combinatorics

KW - sumsets

UR - http://www.scopus.com/inward/record.url?scp=85217737585&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85217737585&partnerID=8YFLogxK

U2 - 10.1137/24M165569X

DO - 10.1137/24M165569X

M3 - Article

AN - SCOPUS:85217737585

SN - 0895-4801

VL - 39

SP - 314

EP - 326

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

SUMSETS IN THE HYPERCUBE

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this