6
$\begingroup$

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.)

$\endgroup$
5
  • 1
    $\begingroup$ Look for literature on brackets in number theory (as opposed to brackets in other fields). Two texts that touch on the treatment are Concrete Mathematics by Graham, Knuth, and Patashnik, and (title something like) Number Theory, an elementary approach by Joe Roberts. The latter is the only calligraphed science text I know, and if you can find its bibliography and a decent citation index, you should likely succeed in finding newer texts that deal with floor and ceiling. Gerhard "Ask Me About Elementary Mathematics" Paseman, 2013.04.14 $\endgroup$ Apr 14, 2013 at 22:55
  • $\begingroup$ @Gerhard Thanks. Please feel free to upgrade that to an answer. $\endgroup$
    – Rhubbarb
    Apr 15, 2013 at 8:43
  • 2
    $\begingroup$ Your special equation you can first solve $\bmod c$, and then use a solution $s\in \mathbb{Z}$ to write $a = s+a'$ where $a'$ is a multiple of $c$. Now solve for $a'$. $\endgroup$
    – Someone
    Apr 15, 2013 at 12:14
  • $\begingroup$ @Someone thanks for your comment - a useful suggestion associated with my question $\endgroup$
    – Rhubbarb
    Apr 16, 2013 at 12:28
  • $\begingroup$ UPDATE: it turns out that the '2' in my equation is significant. I've put some notes on this on my blog rhubbarb.wordpress.com/2013/04/30/inverting-floor $\endgroup$
    – Rhubbarb
    Apr 30, 2013 at 23:02

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @Gerhard and @Aaron - you might like to know that I have just bought myself a (used) copy of Joe Roberts' Elementary Number Theory, and am very please with it. (I do also have a copy of Concrete Mathematics, and agree that that too is an excellent source, which I have also gone back to.) $\endgroup$
    – Rhubbarb
    Apr 28, 2013 at 19:50
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ @Aaron and @Gerhard - you might like to know that I have just bought myself a (used) copy of Joe Roberts' Elementary Number Theory, and am very please with it. I also made use of your scan link as having an electronic copy is also very useful. $\endgroup$
    – Rhubbarb
    Apr 28, 2013 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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