Talk:Basis Representation Theorem

Possible simple clarification needed in proof?

If I'm reading the proof right, then shouldn't the following statement ...

---snip---

So this inequality implies the following:

$\forall m, n: s_b \left({m}\right) \le s_b \left({m - 1}\right) \le \ldots \le s_b \left({n + 1}\right) \le s_b \left({n}\right)$

---snip---

... specify that m >= n? Perhaps like this?

---edit---

So this inequality implies the following:

$\forall m \ge n: s_b \left({m}\right) \le s_b \left({m - 1}\right) \le \ldots \le s_b \left({n + 1}\right) \le s_b \left({n}\right)$

---end---

...or maybe this is clearer...

---edit---

So this inequality implies the following:

$\forall m, n : m \ge n : s_b \left({m}\right) \le s_b \left({m - 1}\right) \le \ldots \le s_b \left({n + 1}\right) \le s_b \left({n}\right)$

---end---

However I'm unsure about my proofwiki style ...

That's all! BTW - pretty nifty proof.

Possibly. The source work containing this proof (Andrews) is arbitrarily fussy: it goes to $s_b \left({m - 2}\right) \le \cdots \le s_b \left({n + 2}\right)$ and specifies $m \ge n + 4$, but I found that unnecessarily inelegant. --prime mover (talk) 16:31, 27 November 2016 (EST)

Thanks for the reply. Curious - why do you suppose Andrews was so fussy? It doesn't seem necessary, the edit you just made to improve the proof seems both necessary and sufficient.

It seems that our use of ellipsis in a statement such as $m, m-1, m-2, ..., n+2, n+1, n$ after you've specified $m \ge n$ shouldn't preclude the sequence from collapsing down to the boundary case when $m = n$ so long as it doesn't create some kind of logical quandary elsewhere no? --Jrowellfx (talk) 19:30, 27 November 2016 (EST)

The point is that you can make $m$ and $n$ whatever you want them to be. The line is, itself, simply an explanatory amplification of the fact that "smaller numbers have no fewer representations than larger numbers" and the line could be replaced with "$m \ge n \implies s_b \left({m}\right) \le s_b \left({n}\right)$" -- which, if you want to make that ultra-rigorously explicit, can of course be hammered out in an induction proof. Could be done, but this particular presentation of this proof keeps close to the spirit of the original. --prime mover (talk) 01:09, 28 November 2016 (EST)

Separating theorem and definition

Is this a candidate for separating theorem and definition? --barto (talk) 11:31, 12 July 2017 (EDT)

Yes in theory, but in practice I haven't got it together to work out a neat way of doing it. Note we also have Definition:Basis Expansion and then we have Basis Representation Theorem for Ordinals and at that point I lost the will to live. --prime mover (talk) 12:24, 12 July 2017 (EDT)

Haha, I understand. Good to know there's a version for ordinals. --barto (talk) 12:42, 12 July 2017 (EDT)

Done. --prime mover (talk) 04:52, 3 September 2019 (EDT)

Earliest known version of this theorem/proof?

Does anyone have an idea where this theorem first showed up? We've been counting in base-ten for almost two thousand years, but when did we first formalize it? I suspect it was fairly recently. --Jrowellfx (talk) 15:42, 24 July 2017 (EDT)

Well I've googled but haven't got any answers. From my own experience, the George Andrews work is the only one I've seen this in, and every citation of the proof is either of Andrews or our very own $\mathsf{Pr} \infty \mathsf{fWiki}$ one which is basically a slightly amplified version of Andrews' proof. It's not even in Knuth, which surprised me.

All I can say is: it can't have been much before Fibonacci. --prime mover (talk) 17:16, 24 July 2017 (EDT)

Indeed, my Google searches didn't turn up much either which is why I turned to y'all here. Agreed wrt Fibonacci's timeframe, seems like a safe lower bound.

I checked my copy of Andrews' "Number Theory" (which is first published in 1971) and found a reference to an earlier article he wrote in the "American Mathematical Monthly" in 1969 entitled "On Radix Representation and the Euclidean Algorithm". I went into the archives online - the article appeared in Jan 1969, p66-68. Indeed the theorem is there and he makes reference to an earlier work. Namely: "E. Landau, Elementary Number Theory, Chelsea NY, 1958", Chp 1, page 13, Theorem 8. Amazon has this book and via "Look inside" there's the theorem on page 13. So... this is the earliest we have so far. Curious if anyone knows of anything before 1958, or if they have a copy of Landau's book that the references might have something earlier. --Jrowellfx (talk) 19:55, 24 July 2017 (EDT)

Update: Perhaps this is a better lower bound...? Leibniz - as he introduced binary to the world. --Jrowellfx (talk) 20:42, 24 July 2017 (EDT)

He may have introduced binary to the world, but did he prove the BRT? --prime mover (talk) 01:13, 25 July 2017 (EDT)

I've just taken that Andrews paper down and studied it myself. His comment "It is standard procedure in books on elementary number theory to prove [BRT]" so clearly Landau isn't the original source of some proof of it. But the elegant proof given here may well be Andrews' original work. --prime mover (talk) 03:25, 25 July 2017 (EDT)

Question

In the statement of the theorem the sequence $\sequence {r_i}$ ranges from $0$ to $m$, whereas the summation ranges from $0$ to $k$. Does $m = k$ and should this not be stated? If $m \neq k$, what is $m$ then?

Should the theorem not be:

Let $b \in \Z: b > 1$.

For every $n \in \Z_{> 0}$, there exists one and only one sequence $\sequence {r_j}_{0 \mathop \le j \mathop \le k}$ such that:

$(1): \quad \displaystyle n = \sum_{j \mathop = 0}^k r_j b^j$

$(2): \quad \displaystyle \forall j \in \closedint 0 k: r_j \in \N_b$

$(3): \quad r_k \ne 0$

This unique sequence is called the representation of $n$ to the base $b$, or, informally, we can say $n$ is (written) in base $b$.

—Leigh.Samphier (talk) 04:20, 22 October 2019 (EDT)

I've been through and corrected the main exposition of the result to match the letters in the proof itself.

Proposed improvement to readability

I understand that in the statement:

So this inequality implies the following:

$\forall m, n: \map {s_b} m \le \map {s_b} {m - 1} \le \ldots \le \map {s_b} {n + 1} \le \map {s_b} n$

given that $m \ge n$.

that the $n$ is in a new scope following the $\forall$ and therefore is not the same $n$ as used throughout the proof. But I am of the opinion that the readability of the proof would be improved if a different variable name were used.

For instance:

So this inequality implies the following:

$\forall m, l: \map {s_b} m \le \map {s_b} {m - 1} \le \ldots \le \map {s_b} {l + 1} \le \map {s_b} l$

given that $m \ge l$.

—Leigh.Samphier (talk) 17:27, 22 October 2019 (EDT)

Yeah I saw this, sorry I'll get round to looking at it to check it against the source work. You'r probably right, I've just not been in a position to do anything about it. --prime mover (talk) 03:56, 23 October 2019 (EDT)

IMO adding more letters makes it even more confusing. I like it the way it is. I've clarified the scope of the variables in the statement. --prime mover (talk) 04:13, 23 October 2019 (EDT)