Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The linear combinations $\lfloor x \rfloor - 2 \lfloor \frac{x}{2} \rfloor$ and $\lfloor x \rfloor - \lfloor \tfrac{x}{2} \rfloor - \lfloor \tfrac{x}{3} \rfloor - \lfloor \tfrac{x}{5} \rfloor + \lfloor \tfrac{x}{30} \rfloor$ can be shown to take values only in $\{ 0, 1 \}$, where $\lfloor \cdot \rfloor$ denotes the floor function.

I'd like to compute arbitrarily long linear combinations of this type, namely, $\sum_{k = 0}^{n} a_k \lfloor b_k x \rfloor$, where $a_k, b_k \in \mathbb{Q}^{\times}$. It is necessary but not sufficient that the sequence $\{a_k, b_k \}$ satisfy the condition $\sum_{k = 0}^{n} a_{k} b_k = 0$. Perhaps I'm missing something simple, but I don't quite see a general method of generating such functions beyond a brute force (and time consuming) search.

share|cite|improve this question
up vote 2 down vote accepted

If I understand the introduction to his paper correctly, the classification of such linear combinations has been completed by Bober following earlier work of Vasyunin. The arbitrary long linear combinations you ask for don't exist

share|cite|improve this answer

It is indeed one of several necessary conditions that $\sum a_k b_k=0$.

Lemma Assume that $f(x) =\sum_{k=0}^n a_k\left\lfloor b_k x\right\rfloor$ with $a_k, b_k\in\mathbb Q^\times$ has the property that $f(x)\in\{0,1\}$ for all $x\in \mathbb R$. Then $$\sum_{k=0}^n a_k b_k = 0\qquad \mathrm{and}\qquad\sum_{k=0}^n a_k\in\{0, -1, -2\}.$$ If the restriction of $f$ to $\mathbb R\setminus\mathbb Q$ is not constant, then $$\sum_{k=0}^n a_k= -1.$$

Proof: Let $h = \sum a_k b_k$. Note that $b_k x -1< \lfloor b_k x\rfloor <b_kx$. Hence $\left|b_k x-\lfloor b_k x\rfloor\right|<1$ and $$\left|\sum a_k\lfloor b_k x\rfloor -hx\right|<\sum |a_k|.$$ Therefore $\sum a_k\lfloor b_k x\rfloor \in\{0,1\}$ would imply $$ hx<1+\sum |a_k|.$$ If $h\ne0$ this cannot hold for all $x$. This shows the first claim.

If $t\notin \mathbb Z$ then $\lfloor-t\rfloor +\lfloor t\rfloor= -1$. Therefore, if $xb_k\notin \mathbb Z$ for all $k$ (e.g. if $x$ is irrational), then $$\tag{1}f(x)+f(-x) =\sum_{k=0}^n a_k\left\lfloor b_k x\right\rfloor+\sum_{k=0}^n a_k\left\lfloor -b_k x\right\rfloor = \sum_{k=0}^n a_k\cdot(-1)$$ Since the left hand side is $\in\{0,1,2\}$, the second claim follows. If there are irrational numbers $x_0$ and $x_1$ with $f(x_0)=0$ and $f(x_1)=1$, then letting $x=x_0$ in (1), the left hand side is $\le 1$ and with letting $x=x_1$ it is $\ge1$, thus showing the third claim. $_\blacksquare$

share|cite|improve this answer
It is also easy to see that it is not sufficient, since $a_1=a_2=1$, $b_1=-b_2=1$ fulfils that condition, but for $x=0.5$ we get $\lfloor 0.5\rfloor + \lfloor -0.5\rfloor = 0 + (-1) = -1 \notin \{0,1\}$. – celtschk Sep 12 '12 at 17:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.