Unions of intervals in codes based on powers of sets

2024/08/27 by Thomas Karam, Karam, Thomas · 1 citation
Computer Science · Engineering · #05D05 #05D10 #94B25 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2408.15144

openalex publication_date 2024/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for every integer d ≥ 2 there exists a dense collection of subsets of [n]^d such that no two of them have a symmetric difference that may be written as the dth power of a union of at most \lfloor d/2 \rfloor intervals. This provides a limitation on reasonable tightenings of a question of Alon from 2023 and of a conjecture of Gowers from 2009, and investigates a direction analogous to that of recent works of Conlon, Kamčev, Leader, Räty and Spiegel on intervals in the Hales-Jewett theorem.

Cited by

• Polynomial maps which are not good for nice recurrence and applications

Related

• Sidon sets in a union of intervals
• Fuglede's conjecture for a union of two intervals
• VC dimension and a union theorem for set systems
• On tiling the integers with 4-sets of the same gap sequence
• Integer sets with identical representation functions