Waring's theorem for binary powers

DOI10.1007/S00493-019-3933-3MaRDI QIDQ2300161zbMATH OpenOpenAlexFDO

Authors Carlo Sanna, Daniel M. Kane, Jeffrey Shallit

Publication date 26 February 2020

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.04483

zbMATH Keywords

sums of binary k-th powers

Mathematics Subject Classification ID

Additive bases, including sumsets (11B13) Waring's problem and variants (11P05) Combinatorics on words (68R15)

Abstract: A natural number is a binary $k$'th power if its binary representation consists of $k$ consecutive identical blocks. We prove an analogue of Waring's theorem for sums of binary $k$'th powers. More precisely, we show that for each integer $kgeq2$, there exists a positive integer $W(k)$ such that every sufficiently large multiple of $E_k:=gcd(2^k-1,k)$ is the sum of at most $W(k)$ binary $k$'th powers. (The hypothesis of being a multiple of $E_k$ cannot be omitted, since we show that the $gcd$ of the binary $k$'th powers is $E_k$.) Also, we explain how our results can be extended to arbitrary integer bases $b>2$.

Review text

The authors consider an interesting variation on Waring's theorem, where the ordinary notion of integer power is replaced by a related notion inspired from formal language theory. More precisely, a positive integer \(N\) is a base-\(b\) \(k\)-th power if its base-\(b\) representation consists of \(k\) consecutive identical blocks. The main result of the paper says that for each integer \(k\geq1\), there exists an effectively computable positive integer \(n\) such that every sufficiently large multiple of \(E_k:=\gcd(2^k-1,k)\) is the sum of at most \(n\) binary \(k\)-th powers. Here notice that the GCD of the binary \(k\)-th powers is \(E_k\). Moreover, they show that the least such \(n\) is \(2^{O(k^2)}\). What concerns the bound it can be improved, the authors conjecture that every positive integer \(>147615\) is the sum of at most nine binary cubes and that the total number of exceptions is 4921. What concerns the basis, they say that analogous results to the main result hold for arbitrary integer bases \(b\geq2\).

Recommendations

• On Waring's problem for intermediate powers
• Extending Waring's Conjecture to 471,600,000
• scientific article; zbMATH DE number 6686838
• An ideal Waring problem with restricted summands
• A variant of Waring's problem

Cited in

(7)

• Additive number theory via automata theory
• A variant of Waring's problem
• When is an automatic set an additive basis?
• ADDITIVE BASES AND NIVEN NUMBERS
• Extending Waring's Conjecture to 471,600,000
• The largest entry in the inverse of a Vandermonde matrix
• The power of the binary value principle

This page was built for publication: Waring's theorem for binary powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300161)