10
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Could you please point me towards the Kolmogoroff complexity based proof of the infinitude of primes? $\endgroup$
    – Martin Berger
    Commented Sep 3, 2013 at 9:10
  • 2
    $\begingroup$ @MartinBerger: see Li and Vitanyi book, or this note by Lance Fortnow $\endgroup$
    – Marzio De Biasi
    Commented Sep 3, 2013 at 9:35
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Subhayan
    Commented Sep 3, 2013 at 10:00
  • $\begingroup$ [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 $\endgroup$
    – Subhayan
    Commented Sep 3, 2013 at 10:01
  • 2
    $\begingroup$ 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 $\endgroup$
    – Sasho Nikolov
    Commented Sep 4, 2013 at 11:06

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Oct 10, 2013 at 1:32
0
$\begingroup$

Number theory is generally concerned with integer equations, though note wikipedia states, 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)."

here are two papers generally along those lines:

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Commented Sep 5, 2013 at 1:02
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Sep 5, 2013 at 2:46
  • $\begingroup$ 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.. $\endgroup$
    – Subhayan
    Commented Sep 5, 2013 at 12:31
-2
$\begingroup$

try this reference

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 of an information source. entropy is used heavily in cryptography as a measure related to randomness, eg see Some Notions of Entropy for Cryptography 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, 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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ -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. $\endgroup$
    – Sasho Nikolov
    Commented Sep 4, 2013 at 9:32
  • $\begingroup$ agreed on that point, oops =( $\endgroup$
    – vzn
    Commented Sep 4, 2013 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.