Skip to main content
added 1148 characters in body; added 3 characters in body; added 2 characters in body; edited body
Source Link
fedja
  • 61.9k
  • 11
  • 160
  • 302

Not thatOK, by Seva's request I'm getting somewhat more serious about this answer:) Fix $a$, but yes$b$. Take anlarge $N$$M$ to be chosen shortly. Take a $3MN$ digit number $n$ (something from $0$ to $10^{3MN}-1$, written with head zeroes if necessary) and split its decimal representation into pieces of length $3M$ where $M$ is large but fixed. A noticeable portion ofLet us call these $3M$-digit pieces will be of$n_k$ so $n=\sum_{k=0}^{N-1}10^{3Mk}n_k$. Consider $n_k$ as independent random variables uniformly distributed in the kindset $M$ zeroes$\{0,1,2,\dots,10^{3M}-1\}$. By the law of large numbers, somethingwith probability close to $1$, there are about $M$ zeroes.$N\cdot 10^{-2M}$ pieces $n_k$ that start and end with $M$ zeroes will control(with the transfers ifmiddle $M$ is large enough and, conditioning upondigits being anything). Call the location of thesenumbers $n$ that satisfy this property typical. The typical numbers can be split into groups according to exactly which $k$ correspond to such pieces (denote by $K$ the set of all such $k$) and what number is formed by the restdigits outside these groups (that number is $n'=\sum_{k\notin K}10^{3Mk}n_k$). We need to show that in each group $G=G(K,n')$ of typical numbers the representationportion of the solutions is small.

As Fedor explained, we see that these pieces will give us long sumsif $M$ exceeds the number of independentdigits in $a$, we have $s(an)=s(an')+\sum_{k\in K}s(an_k)$ and similarly for $b$. Thus $$ s(an)-s(bn)=s(an')-s(bn')+\sum_{k\in K}X_k $$ with $$ X_k=s(an_k)-s(bn_k) $$ The random variables $X_k$ are i. Nowi.d. and their distribution is completely determined by $a,b$, we need 3 statements:and $M$.

  1. If $X$ is an integer-valued random variable with finitely many values that is not constant, then $\lim_{N\to\infty}\sup_{k\in\mathbb Z} P\{\sum_{i=1}^N X_i=k\}=0$ where $X_i$ are i.i.d. random variables equidistributed with $X$.

  2. If $s(an)-s(bn)=C$ for all $n$ (i.e., if we cannot choose $M$ to use Claim 1), then $C=0$.

  3. If $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end.

Claim 3 isSuppose that the only non-obviousequality $s(an)=s(bn)$ fails for at least one $n\ge 0$. I doThen (since it holds for $n=0$) $X_k$ is not have a decent proofconstant for sufficiently large $M$ and we can use the following

Probabilistic Claim. If $X$ is any fixed integer-valued random variable with finitely many values that is not constant, then $\lim_{Q\to\infty}\sup_{S\in\mathbb Z} P\{\sum_{k=1}^Q X_k+S=0\}=0$ where $X_k$ are i.i.d. random variables equidistributed with $X$.

Since the cardinality $Q$ of it yet (if I find one while I'm driving$K$ for every typical group is huge when $N$ is large enough, we conclude that the above displayed equation has very little chance to workhold in every typical group $G(K,n')$ and, I'll post itthereby, butoverall.

However, most likelyif $s(an)=s(bn)$ for all $n$, someone else will beat me to that)then $a$ and $b$ differ only by the number of zeroes in the end.

I apologize if this edit rendered some comments meaningless.

Not that I'm serious about this answer, but yes. Take an $N$ digit number $n$ and split its decimal representation into pieces of length $3M$ where $M$ is large but fixed. A noticeable portion of these pieces will be of the kind $M$ zeroes, something, $M$ zeroes. $M$ zeroes will control the transfers if $M$ is large enough and, conditioning upon the location of these pieces and the rest of the representation, we see that these pieces will give us long sums of independent variables. Now, we need 3 statements:

  1. If $X$ is an integer-valued random variable with finitely many values that is not constant, then $\lim_{N\to\infty}\sup_{k\in\mathbb Z} P\{\sum_{i=1}^N X_i=k\}=0$ where $X_i$ are i.i.d. random variables equidistributed with $X$.

  2. If $s(an)-s(bn)=C$ for all $n$ (i.e., if we cannot choose $M$ to use Claim 1), then $C=0$.

  3. If $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end.

Claim 3 is the only non-obvious one. I do not have a decent proof of it yet (if I find one while I'm driving to work, I'll post it, but, most likely, someone else will beat me to that).

OK, by Seva's request I'm getting somewhat more serious :) Fix $a$, $b$. Take large $M$ to be chosen shortly. Take a $3MN$ digit number $n$ (something from $0$ to $10^{3MN}-1$, written with head zeroes if necessary) and split its decimal representation into pieces of length $3M$ where $M$ is large but fixed. Let us call these $3M$-digit pieces $n_k$ so $n=\sum_{k=0}^{N-1}10^{3Mk}n_k$. Consider $n_k$ as independent random variables uniformly distributed in the set $\{0,1,2,\dots,10^{3M}-1\}$. By the law of large numbers, with probability close to $1$, there are about $N\cdot 10^{-2M}$ pieces $n_k$ that start and end with $M$ zeroes (with the middle $M$ digits being anything). Call the numbers $n$ that satisfy this property typical. The typical numbers can be split into groups according to exactly which $k$ correspond to such pieces (denote by $K$ the set of all such $k$) and what number is formed by the digits outside these groups (that number is $n'=\sum_{k\notin K}10^{3Mk}n_k$). We need to show that in each group $G=G(K,n')$ of typical numbers the portion of the solutions is small.

As Fedor explained, if $M$ exceeds the number of digits in $a$, we have $s(an)=s(an')+\sum_{k\in K}s(an_k)$ and similarly for $b$. Thus $$ s(an)-s(bn)=s(an')-s(bn')+\sum_{k\in K}X_k $$ with $$ X_k=s(an_k)-s(bn_k) $$ The random variables $X_k$ are i.i.d. and their distribution is completely determined by $a,b$, and $M$.

Suppose that the equality $s(an)=s(bn)$ fails for at least one $n\ge 0$. Then (since it holds for $n=0$) $X_k$ is not a constant for sufficiently large $M$ and we can use the following

Probabilistic Claim. If $X$ is any fixed integer-valued random variable with finitely many values that is not constant, then $\lim_{Q\to\infty}\sup_{S\in\mathbb Z} P\{\sum_{k=1}^Q X_k+S=0\}=0$ where $X_k$ are i.i.d. random variables equidistributed with $X$.

Since the cardinality $Q$ of $K$ for every typical group is huge when $N$ is large enough, we conclude that the above displayed equation has very little chance to hold in every typical group $G(K,n')$ and, thereby, overall.

However, if $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end.

I apologize if this edit rendered some comments meaningless.

Source Link
fedja
  • 61.9k
  • 11
  • 160
  • 302

Not that I'm serious about this answer, but yes. Take an $N$ digit number $n$ and split its decimal representation into pieces of length $3M$ where $M$ is large but fixed. A noticeable portion of these pieces will be of the kind $M$ zeroes, something, $M$ zeroes. $M$ zeroes will control the transfers if $M$ is large enough and, conditioning upon the location of these pieces and the rest of the representation, we see that these pieces will give us long sums of independent variables. Now, we need 3 statements:

  1. If $X$ is an integer-valued random variable with finitely many values that is not constant, then $\lim_{N\to\infty}\sup_{k\in\mathbb Z} P\{\sum_{i=1}^N X_i=k\}=0$ where $X_i$ are i.i.d. random variables equidistributed with $X$.

  2. If $s(an)-s(bn)=C$ for all $n$ (i.e., if we cannot choose $M$ to use Claim 1), then $C=0$.

  3. If $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end.

Claim 3 is the only non-obvious one. I do not have a decent proof of it yet (if I find one while I'm driving to work, I'll post it, but, most likely, someone else will beat me to that).