References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Question

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good references on solving equations of this sort.

I had an equation

$2 \lfloor a \rfloor_{c} - a = d - c$

with $a,c,d \in {\mathbb Z} $, and where $\lfloor n \rfloor_{k}$ is my notation for $k \lfloor n/k \rfloor$ — essentially the floor function down to the nearest multiple of $k$.

I wished to solve for $a$. Now, I didn't know how to tackle this algebraically, as the usual technique of bringing the $a$'s together does not seem to be available. However, I had some notion of what form a solution was likely to take. After some guesswork and experimentation with Maxima, I found the solution:

$a = 2 \lceil d \rceil_{c} - (c + d)$

This appears to be correct, but I have not yet found a way to prove this — but that's not my question.

This approach is very unsatisfactory to me. I would much rather solve the problem algbraically.

I'd like to know if there are any recommended references, either books or on-line, about techniques that can be used to solve equations involving the floor ($\lfloor \cdot \rfloor$), ceiling ($\lceil \cdot \rceil$), fraction-part, and similar functions, either in ${\mathbb Z}$, ${\mathbb Q}$ or ${\mathbb R}$.

Beyond my particular equation of interest, I'd be interested to learn how to tackle this sort of equation more generally.

(In case you're interested why I was looking at this equation: I have recently encountered the remarkable Stern diatomic sequence. The equation in question is related to the successor function on ratios of consecutive terms; I wished to find the inverse function.)

Answer 1

Joe Roberts provided the words for the calligraphed book Elementary Number Theory: A Problem Oriented Approach, which was printed in the 1970's. This book has a chapter on brackets, which in some of the number theory literature is an older name for one or both of the floor and ceiling functions. While not providing as focused a treatment of brackets, Concrete Mathematics, which was authored by Graham, Knuth, and Patashnik, also gives some service to the handling of floor and ceiling. With the bibliographies of those two books and a decent citation index, you may find more recent treatments. There may be other search terms to use, but I would start with "brackets +number theory -Lie" or something like that in a web search.

Gerhard "Is It Forty Years Already?" Paseman, 2013.04.15

Answer 2

Expressions formed by composing polynomials and the integer-part operator are refered to in numerous papers by the not very google-friendly name ``generalized polynomials''. The problem of determining whether a generalized polynomial equation has integer solutions includes Hilbert's Tenth problem, and is therefore effectively unsolvable. On the other hand there are some interesting results on the distribution of values of generalized polynomials, which you might find relevant:

1. Bergelson and Leibman's paper ``Distribution of values of bounded generalized polynomials'' available here.

2. Leibman's paper ``A canonical form and the distribution of values of generalized polynomials'' available here.

There are related papers on Leibman's website and also by Haland and McCutcheon. Leibman's paper gives a cannonical form for generalized polynomials that helps to grasp what values the gp can assume mod 1. His paper is a follow-up to the Bergelson-Leibman paper, in which Bergelson shows very roughly speaking that every bounded generalized polynomial can be thought of as a matrix power map composed with a piecewise-polynomial function. Bergelson shows how tools from Ergodic Theory and Lie Theory can be brough to bear on the study of generalized polynomials.

Incidentally, the problem of which equations $g=0$ are identities (i.e. hold for all integer values of the variables), where g is a gp, is also effective unsolvable by reduction to Hilbert's Tenth Problem: Let $f$ be any polynomial with integer coefficients. Then the equation $$\lfloor \sqrt{2}f(\bar{x})\rfloor+\lfloor- \sqrt{2}f(\bar{x})\rfloor+1=0$$ is an identity if and only if $f$ has no integer zeros.

Answer 3

I agree that the Joe Roberts book is a gem. I've bought two copies over the years. I'd buy a third if I could. Here is a link to a scan I leave ethical issues to you, I got this from another MO answer .

That said, the Wikipedia article may cover the same material (but check for yourself). The main reference for that article seems to be the Graham, Knuth, and Patashnik book so that would be more reliable.

There are various easily verified equations and inequalities such as

$$\Big\lceil \frac{m}{n} \Big\rceil=\Big\lfloor \frac{m+n-1}{n}\Big\rfloor=\Big\lfloor \frac{m-1}{n}\Big\rfloor+1$$ (which would give an alternate form to your answer which you might or might not prefer.) Then it is a matter of practice.

Actually I see that that particular page say "then use a geometric arguement" in discussing quadratic reciprocity. The Joe Roberts book does give the arguement.