Almost Beatty partitions

zbMATH Open1418.11044arXiv1809.08690MaRDI QIDQ5226858FDOQ5226858

Authors: Xiao-Min Li, Junxian Li, Yun Xie, Adolf Hildebrand 

Publication date: 2 August 2019

Abstract: Given $0<alpha<1$, the Beatty sequence of density $alpha$ is the sequence $B_{alpha}=(lfloorn/alphafloor{)}_{ninmathbbN}$. Beatty's theorem states that if $$ are irrational numbers with $$, then the Beatty sequences $B_{alpha}$ and $$ partition the positive integers, that is, each positive integer belongs to exactly one of these two sequences. On the other hand, Uspensky showed that this result breaks down completely for partitions into three (or more) sequences: There does not exist a single triple $$ such that the Beatty sequences $$ partition the positive integers. In this paper we consider the question of how close we can come to a three-part Beatty partition by considering "almost" Beatty sequences, that is, sequences that represent small perturbations of an "exact" Beatty sequence. We first characterize all cases in which there exists a partition into two exact Beatty sequences and one almost Beatty sequence with given densities, and we determine the approximation error involved. We then give two general constructions that yield partitions into one exact Beatty sequence and two almost Beatty sequences with prescribed densities, and we determine the approximation error in these constructions. Finally, we show that in many situations these constructions are best-possible in the sense that they yield the closest approximation to a three-part Beatty partition.

Full work available at URL: https://arxiv.org/abs/1809.08690

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Partitions into Beatty sequences
• Interpolating classical partitions of the set of positive integers
• Partitioning the positive integers to seven Beatty sequences
• A generalization of Beatty's theorem
• Gap problems for integer part and fractional part sequences

zbMATH Keywords

Beatty sequencecomplementary sequencepartition of the integers

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Special sequences and polynomials (11B83) Elementary theory of partitions (11P81)

Cites Work

• The on-line encyclopedia of integer sequences
• On certain distributions of integers in pairs with given differences
• Title not available (Why is that?)
• The Chairman assignment problem
• Beatty Sequences, Continued Fractions, and Certain Shift Operators
• The Bracket Function and Complementary Sets of Integers
• On A Theorem of Uspensky
• A generating function technique for Beatty sequences and other step sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the sequence $[n \alpha]$, $n = 1,2,\dots$. Supplementary note to the preceding paper by Th. Skolem
• Iterated Floor Function, Algebraic Numbers, Discrete Chaos, Beatty Subsequences, Semigroups
• The optimality of the online greedy algorithm in carpool and chairman assignment problems
• The Fifty-Eighth William Lowell Putnam Mathematical Competition
• Generalized Beatty sequences and complementary triples
• A Model for Pairs of Beatty Sequences
• Complementary Systems of Integers
• Slow Beatty Sequences, Devious Convergence, and Partitional Divergence
• Complementary equations and Wythoff sequences
• On functions expressible as words on a pair of Beatty sequences
• Title not available (Why is that?)
• Complementary iterated floor words and the Flora game
• A generalization of Beatty's theorem
• Title not available (Why is that?)

Cited In (8)

• Partitions into Beatty sequences
• Title not available (Why is that?)
• Partitioning the positive integers to seven Beatty sequences
• Webster sequences, apportionment problems, and just-in-time sequencing
• A generalization of Beatty's theorem
• A discrete Fourier kernel and Fraenkel's tiling conjecture
• Gap problems for integer part and fractional part sequences
• Interpolating classical partitions of the set of positive integers

Uses Software

• OEIS

This page was built for publication: Almost Beatty partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226858)