<p>Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer.</p>

<p>There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$    vs  $\approx ln(x)$.</p>

<p>As a side effect you have to have some large gaps between primes; otherwise you could encode every number as the previous prime plus some small number of bits.</p>

CC BY-SA 3.0
2013-10-10T01:32:59.940Z
There are large gaps between primes because of the prime number theorem, I don't think you need to add Kolmogorov complexity in the mix to show that.
Sasho Nikolov
CC BY-SA 3.0
2013-10-09T17:42:05.207Z
2013-10-09T17:48:52.780Z
2013-10-09T17:48:52.780Z
Chad Brewbaker
<p>Number theory is generally concerned with integer equations, though note <a href="http://en.wikipedia.org/wiki/Number_theory" rel="nofollow">wikipedia states</a>, more broadly, a subbranch of number theory is the approximation of reals by rationals and the relation between them: "One may also study real numbers in relation to rational numbers, e.g., as approximated by the latter (<a href="http://en.wikipedia.org/wiki/Diophantine_approximation" rel="nofollow">Diophantine approximation</a>)."</p>

<p>here are two papers generally along those lines:</p>

<ul>
<li><p><a href="http://www.sciencedirect.com/science/article/pii/S0304397501001025" rel="nofollow">The Kolmogorov complexity of real numbers</a> Ludwig Staiger</p></li>
<li><p><a href="http://www.sciencedirect.com/science/article/pii/S0304397501000275" rel="nofollow">A characterization of c.e. random reals</a> Cristian S. Calude</p></li>
</ul>

CC BY-SA 3.0
2013-09-05T01:02:01.223Z
What part of Komolgorov complexity can't apply to integer equations?  While it's true that the subject often concerns itself with the infinite, number theory can as well (e.g., diophantine equations, etc.) and of course there are various resource-bounded versions of KC that can be relevant, etc.  I'm just not sure where 'Number theory is generally concerned with integer equations' has anything to do with whether there are applications of KC to the topic.
Steven Stadnicki
CC BY-SA 3.0
2013-09-05T02:46:59.093Z
the point is that on a cursory online search I didnt [yet?] find refs very directly relating KC to number theory, but there are some relating it to analyzing reals & rational approximations in a way that borders on number theory.
vzn
CC BY-SA 3.0
2013-09-05T12:31:23.463Z
yes, I too tried to look up about applications of KC in number theory, however I could not find anything, now KC seems to be a nice way to tackle some problems in number theory.. there ought to be some fundamental proofs(applications) here..
Subhayan
CC BY-SA 3.0
2013-09-04T16:12:43.307Z
2013-09-04T16:12:43.307Z
vzn
<p>try this reference</p>

<ul>
<li><a href="http://link.springer.com/chapter/10.1007%2F978-3-540-36351-4_5" rel="nofollow">From Kolmogorov’s theorem on empirical distribution to number theory</a>, Kevin Ford, also <a href="http://www.math.uiuc.edu/~ford/wwwpapers/kol.pdf" rel="nofollow">here</a>.</li>
</ul>

<blockquote>
  <p>We describe some new estimates for the probabiity that an empirical distribution function stays on one side of a given line, and give applications to number theory.</p>
</blockquote>

<ul>
<li><p>sketch of another basic conceptual connection/bridge in cryptography. $K(x)$ is related to the <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity#Relation_to_entropy" rel="nofollow">entropy</a> of an information source. entropy is used heavily in cryptography as a measure related to randomness, eg see <a href="http://www.cs.bu.edu/~reyzin/papers/entropy-survey.pdf" rel="nofollow">Some Notions of Entropy for Cryptography</a> by Reyzin. </p></li>
<li><p>however, <em>caveat</em>, there is no direct reference to Kolmogorov complexity there! and looking at this very long Phd thesis/survey on entropy in cryptography by Cachin/Maurer <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1016" rel="nofollow">Entropy Measures and Unconditional Security in Cryptography</a>, there is no direct reference either! so it appears to me that $K(x)$ is a more "computationally intractable" measurement of entropy and therefore doesnt show up often in cryptography analysis which needs more pragmatic metrics even though it is conceptually linked. there may be a sense in which $K(x)$ is at the same time the strictest measure of entropy and yet at the same time the most intractable, with other entropy measures at other "easier" points in this apparent strict vs. tractable tradeoff continuum.</p></li>
</ul>

CC BY-SA 3.0
2013-09-04T09:32:58.970Z
-1: The Kolmogorov theorem in the first reference is not related to Kolmogorov complexity. It's a famous result about convergence of the empirical distribution function of IID samples to the CDF.
Sasho Nikolov
CC BY-SA 3.0
2013-09-04T16:04:21.067Z
agreed on that point, oops =(
vzn
CC BY-SA 3.0
2013-09-03T15:29:48.340Z
2013-09-03T15:29:48.340Z
vzn
<p>What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li &amp; Vitanyi doesn't have many applications related to Number Theory.)</p>

<p>One of the nice proofs i have come across is the proof of the existence of infinite number of primes, using the definition of Kolmogorov Complexity and the compression factor.</p>

<p>Also, what is the importance of Kolmogorov Complexity in Cryptography?</p>

CC BY-SA 3.0
2013-09-03T09:10:06.343Z
Could you please point me towards the Kolmogoroff complexity based proof of the infinitude of primes?
Martin Berger
CC BY-SA 3.0
2013-09-03T09:35:25.157Z
@MartinBerger: see Li and Vitanyi book, or this [note by Lance Fortnow](http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf)
Marzio De Biasi
CC BY-SA 3.0
2013-09-03T10:00:55.297Z
okay, this is a little awkward, but i can't seem to recall where i came across it, the proof goes something like this.. assume you choose an inf. set $$S = {n_1,n_2,...}$$ such that $n$ is positive and $K(n) \geq \frac{log_2 n}{2}$ , $\forall n \in S$. 

Now _for purposes of contradiction_ assume there are only some finite number of primes, ${p_1...p_m}$.
Subhayan
CC BY-SA 3.0
2013-09-03T10:01:24.237Z
_**[contd]**_
So now we can represent any $n_i$ as $\Sigma_{j=1}^{m}p_j^{v_{i,j}}$. 

Since we assumed there are only finitely many ($m$) primes, they have a fixed representation. So $K(n_i)$ only depends upon the $v_{i,j}$ s .. so to sum it up, $K(n_i) = const + \Sigma_{j=1}^{m}\ log_2(v_{i,j}+1)$ ...

which can be at most some $const + m.log_2log_2n_{i}$... 

but then we declared $K(n) \geq \frac{log_2 n}{2}$ $\forall n \in S$. 

**Therefore)** this implies that $\frac{log_2 n_i}{2} \leq m.log_2log_2n_{i}$ but this is true only for a finite number of $n_i$. Hence we arrive at a contradiction
Subhayan
CC BY-SA 3.0
2013-09-04T11:06:56.967Z
I like the second NT example from Lance's notes: that the $k$-th prime number $p_k$ is at most $p_k \leq k\log^2 k$. This is one log off of the prime number theorem, and the proof is about as easy as the proof of the infinitude of primes via K. complexity
Sasho Nikolov
CC BY-SA 3.0
2013-09-04T14:03:24.513Z
yeah, that is elegant !
my favorite would probably be the definition of (kolmogorov) randomness .. that's really brilliant and fundamental.
Subhayan
CC BY-SA 3.0
2013-10-09T19:04:06.100Z
If instead of writing $k$ in extended binary, you first write down the digits of $k$ in extended binary, and then $k$ in binary, then you get $p_k\le k\log k (\log \log k)^2$.
domotorp
CC BY-SA 3.0
2013-10-09T19:10:30.767Z
And btw, the above argument only shows that for some $k$ we have $p_k\le k\log^2k$, it does not prove it for every $k$.
domotorp
<reference-request><big-list><it.information-theory><kolmogorov-complexity>
Kolmogorov Complexity applications in Number Theory
Subhayan
# Kolmogorov Complexity applications in Number Theory

(Asked by: username_0 on 2013-09-01)

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.)

One of the nice proofs i have come across is the proof of the existence of infinite number of primes, using the definition of Kolmogorov Complexity and the compression factor.

Also, what is the importance of Kolmogorov Complexity in Cryptography?

**Tags:** reference-request, big-list, it.information-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: Could you please point me towards the Kolmogoroff complexity based proof of the infinitude of primes?  
> **username_2**: @MartinBerger: see Li and Vitanyi book, or this [note by Lance Fortnow](http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf)  
> **username_0**: okay, this is a little awkward, but i can't seem to recall where i came across it, the proof goes something like this.. assume you choose an inf. set $$S = {n_1,n_2,...}$$ such that $n$ is positive and $K(n) \geq \frac{log_2 n}{2}$ , $\forall n \in S$.   Now _for purposes of contradiction_ assume there are only some finite number of primes, ${p_1...p_m}$.  
> **username_0**: _**[contd]**_ So now we can represent any $n_i$ as $\Sigma_{j=1}^{m}p_j^{v_{i,j}}$.   Since we assumed there are only finitely many ($m$) primes, they have a fixed representation. So $K(n_i)$ only depends upon the $v_{i,j}$ s .. so to sum it up, $K(n_i) = const + \Sigma_{j=1}^{m}\ log_2(v_{i,j}+1)$ ...  which can be at most some $const + m.log_2log_2n_{i}$...   but then we declared $K(n) \geq \frac{log_2 n}{2}$ $\forall n \in S$.   **Therefore)** this implies that $\frac{log_2 n_i}{2} \leq m.log_2log_2n_{i}$ but this is true only for a finite number of $n_i$. Hence we arrive at a contradiction  
> **username_3**: I like the second NT example from Lance's notes: that the $k$-th prime number $p_k$ is at most $p_k \leq k\log^2 k$. This is one log off of the prime number theorem, and the proof is about as easy as the proof of the infinitude of primes via K. complexity  
> **username_0**: yeah, that is elegant ! my favorite would probably be the definition of (kolmogorov) randomness .. that's really brilliant and fundamental.  
> **username_4**: If instead of writing $k$ in extended binary, you first write down the digits of $k$ in extended binary, and then $k$ in binary, then you get $p_k\le k\log k (\log \log k)^2$.  
> **username_4**: And btw, the above argument only shows that for some $k$ we have $p_k\le k\log^2k$, it does not prove it for every $k$.  

---

## 3 answers

### Answer by username_5 on 2013-10-09. Score: 3

Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer.

There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$ vs $\approx ln(x)$.

As a side effect you have to have some large gaps between primes; otherwise you could encode every number as the previous prime plus some small number of bits.

> **Comments:**
> **username_3**: There are large gaps between primes because of the prime number theorem, I don't think you need to add Kolmogorov complexity in the mix to show that.  

---

### Answer by username_6 on 2013-09-04. Score: 0

Number theory is generally concerned with integer equations, though note [wikipedia states](http://en.wikipedia.org/wiki/Number_theory), more broadly, a subbranch of number theory is the approximation of reals by rationals and the relation between them: "One may also study real numbers in relation to rational numbers, e.g., as approximated by the latter ([Diophantine approximation](http://en.wikipedia.org/wiki/Diophantine_approximation))."

here are two papers generally along those lines:

* [The Kolmogorov complexity of real numbers](http://www.sciencedirect.com/science/article/pii/S0304397501001025) Ludwig Staiger
* [A characterization of c.e. random reals](http://www.sciencedirect.com/science/article/pii/S0304397501000275) Cristian S. Calude

> **Comments:**
> **username_7**: What part of Komolgorov complexity can't apply to integer equations?  While it's true that the subject often concerns itself with the infinite, number theory can as well (e.g., diophantine equations, etc.) and of course there are various resource-bounded versions of KC that can be relevant, etc.  I'm just not sure where 'Number theory is generally concerned with integer equations' has anything to do with whether there are applications of KC to the topic.  
> **username_6**: the point is that on a cursory online search I didnt [yet?] find refs very directly relating KC to number theory, but there are some relating it to analyzing reals & rational approximations in a way that borders on number theory.  
> **username_0**: yes, I too tried to look up about applications of KC in number theory, however I could not find anything, now KC seems to be a nice way to tackle some problems in number theory.. there ought to be some fundamental proofs(applications) here..  

---

### Answer by username_6 on 2013-09-03. Score: -2

try this reference

* [From Kolmogorov’s theorem on empirical distribution to number theory](http://link.springer.com/chapter/10.1007%2F978-3-540-36351-4_5), Kevin Ford, also [here](http://www.math.uiuc.edu/~ford/wwwpapers/kol.pdf).

> We describe some new estimates for the probabiity that an empirical distribution function stays on one side of a given line, and give applications to number theory.

* sketch of another basic conceptual connection/bridge in cryptography. $K(x)$ is related to the [entropy](http://en.wikipedia.org/wiki/Kolmogorov_complexity#Relation_to_entropy) of an information source. entropy is used heavily in cryptography as a measure related to randomness, eg see [Some Notions of Entropy for Cryptography](http://www.cs.bu.edu/~reyzin/papers/entropy-survey.pdf) by Reyzin.
* however, *caveat*, there is no direct reference to Kolmogorov complexity there! and looking at this very long Phd thesis/survey on entropy in cryptography by Cachin/Maurer [Entropy Measures and Unconditional Security in Cryptography](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1016), there is no direct reference either! so it appears to me that $K(x)$ is a more "computationally intractable" measurement of entropy and therefore doesnt show up often in cryptography analysis which needs more pragmatic metrics even though it is conceptually linked. there may be a sense in which $K(x)$ is at the same time the strictest measure of entropy and yet at the same time the most intractable, with other entropy measures at other "easier" points in this apparent strict vs. tractable tradeoff continuum.

> **Comments:**
> **username_3**: -1: The Kolmogorov theorem in the first reference is not related to Kolmogorov complexity. It's a famous result about convergence of the empirical distribution function of IID samples to the CDF.  
> **username_6**: agreed on that point, oops =(  

---

