PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Low Entry average rating: No information on entry rating
Fraenkel's partition theorem (Theorem)

Fraenkel's partition theorem is a generalization of Beatty's Theorem. Set

$\displaystyle {\cal B}(\alpha,\alpha^\prime) := \left( \left\lfloor \frac{n-\alpha^\prime}{\alpha} \right\rfloor \right)_{n=1}^\infty. $
We say that two sequences partition $ \mathbb{N}=\{1,2,3,\ldots\}$ if the sequences are disjoint and their union is $ \mathbb{N}$.


Fraenkel's Partition Theorem:The sequences $ {\cal B}(\alpha,{\alpha^\prime})$ and $ {\cal B}(\beta,\beta^\prime )$ partition $ \mathbb{N}$ if and only if the following five conditions are satisfied.

  1. $ 0<\alpha<1$.
  2. $ \alpha+\beta=1$.
  3. $ 0\le\alpha+{\alpha^\prime}\le 1$.
  4. If $ \alpha$ is irrational, then $ {\alpha^\prime}+\beta^\prime =0$ and $ k\alpha+{\alpha^\prime}\not\in\mathbb{Z}$ for $ 2\le k\in \mathbb{N}$.
  5. If $ \alpha$ is rational (say $ q\in \mathbb{N}$ is minimal with $ q\alpha \in \mathbb{N}$), then $ \frac1q \le \alpha+{\alpha^\prime}$ and $ \left\lceil q{\alpha^\prime} \right\rceil +\left\lceil q\beta^\prime \right\rceil =1.$


References

[1]
Aviezri S. Fraenkel, The bracket function and complementary sets of integers, Canad. J. Math. 21 (1969), 6-27. MR 38:3214
[2]
Kevin O'Bryant, Fraenkel's partition and Brown's decomposition, arXiv:math.NT/0305133.



"Fraenkel's partition theorem" is owned by Kevin OBryant.
(view preamble)

View style:

See Also: Beatty sequence, Beatty's theorem, data stream, stream interlace and deinterlace

Other names:  Fraenkel's theorem
Log in to rate this entry.
(view current ratings)

Cross-references: decomposition, integers, complementary, bracket function, References, minimal, rational, irrational, union, disjoint, partition, sequences, Beatty's theorem
There is 1 reference to this entry.

This is version 3 of Fraenkel's partition theorem, born on 2003-06-08, modified 2007-06-23.
Object id is 4333, canonical name is FraenkelsPartitionTheorem.
Accessed 3383 times total.

Classification:
AMS MSC11B83 (Number theory :: Sequences and sets :: Special sequences and polynomials)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)