The asymptotic number of solutions of a diophantine equation from coding theory

Exact enumeration problems, generating functions (05A15) Trees (05C05) Counting solutions of Diophantine equations (11D45) Theory of error-correcting codes and error-detecting codes (94B99)

Review text

Let \(a(n)\) denote the number of solutions of the equation \(2^{-x_1}+\ldots+2^{-x_n} =1\), where the \(x_i\) are integers satisfying \(0\leq x_1\leq\ldots\leq x_n\). This equation occurs in the theory of uniquely decipherable codes (see \textit{B. McMillan}, IRE Trans. Inf. Theory 2, No. 4, 115--116 (1965; Zbl 0137.13503)]). By relating this to a problem of enumerating the labels on certain infinite trees, we are able to show that the generating function for \(\{a(n)\}\) is meromorphic in the unit disk and hence that \(a(n) = \alpha\lambda^n + O(\mu^n)\), where \(\alpha,\lambda\) are positive constants and \(0\leq \mu<\lambda\). The first few terms of the continued fraction expansion of the generating function can be calculated and this gives the following estimates: \[ 1.794147176 < \lambda <1.794147186,\quad a=0.14185325\pm 6\times 10^{-3}, \] and the error term is smaller than \(578(1.55)^n\).

Recommendations

Cites work

Cited in

(7)

This page was built for publication: The asymptotic number of solutions of a diophantine equation from coding theory

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