5 ms·

OK, you can trivially pump numbers with small factors. But what about the numbers that have all prime factors greater than the pumping length?

by jwilk 5y ago

colanderman 5y ago
The above proof is just stating that all nonprimes >= 4 are even, and therefore can be pumped -- so contradiction by pumping lemma does not apply.
- thaumasiotes 5y ago
  Think about what you're saying. You think 15 is an even number? maweki may be thinking that you can divide a string for pumping lemma purposes any way you please. If that were true, you could show that all strings of nonprime length could be pumped while still retaining nonprime length: 1. |s| is composite, so |s| = km for some integers k and m 2. Choose the length of the pumpable substring y to be k. Then |xz| = s - k = k(m-1), and |x y^n z| = k(m-1) + kn = k(m + n - 1). This is composite, so the pumping is valid. The problem, as jwillk has identified, is that the pumping lemma doesn't allow this. The language has a pumping length (traditionally m), and you have to divide your string into three substrings x y z such that all of the following are true: 1. |y| > 0 2. |xz| < m 3. x y^n z remains in the language for all n. Condition (2) prevents us from using the maweki strategy.
thaumasiotes 5y ago
Just to tie everything up, if you have Dirichlet's theorem it's easy to show that {1^x: x not prime} is irregular through a "direct" proof by contradiction using the pumping lemma. 1. Assuming the language is regular, the pumping lemma tells us that it has a pumping length m, and all strings of length at least m can be divided into a prefix x, a suffix z, and a pumpable substring y, such that: 1a. |xz| < m 1b. |y| > 1 1c. The concatenation x y^n z remains in the language for all n. (In this case, this means that |xz| + n*|y| is nonprime for all nonnegative y.) 2. Consider the string c = 1^p², where p is a prime number greater than m[1]. 3. The pumping lemma will divide c into substrings x y z as described above. 4. Observe that |xz| < m < p and |y| = p² - |xz| 5. Dirichlet's theorem tells us that the arithmetic sequence {a + nd} contains infinitely many primes as long as a and d are coprime. Pumping our string c will generate strings with lengths belonging to the arithmetic sequence {|xz| + n(p² - |xz|)}. It remains to be shown that |xz| and (p² - |xz|) are coprime. 6. Observe that any number which divides both (p² - |xz|) and |xz| will also divide [(p² - |xz|) + |xz|] = p². 7. Since p is prime, the only divisors of p² are 1, p, and p². 8. Since |xz| < p, we can see that gcd(|xz|, (p² - |xz|)) = 1. This completes the proof; pumping c is guaranteed to produce not just one but infinitely many strings of prime length. [1] Euclid tells us that there is no greatest prime number, so we can guarantee the existence of such a p.

OK, you can trivially pump numbers with small factors. But what about the numbers that have all prime factors greater than the pumping length?

by jwilk 5y ago

OK, you can trivially pump numbers with small factors. But what about the numbers that have all prime factors greater than the pumping length?

colanderman 5y ago

The above proof is just stating that all nonprimes >= 4 are even, and therefore can be pumped -- so contradiction by pumping lemma does not apply.

thaumasiotes 5y ago
Think about what you're saying. You think 15 is an even number? maweki may be thinking that you can divide a string for pumping lemma purposes any way you please. If that were true, you could show that all strings of nonprime length could be pumped while still retaining nonprime length: 1. |s| is composite, so |s| = km for some integers k and m 2. Choose the length of the pumpable substring y to be k. Then |xz| = s - k = k(m-1), and |x y^n z| = k(m-1) + kn = k(m + n - 1). This is composite, so the pumping is valid. The problem, as jwillk has identified, is that the pumping lemma doesn't allow this. The language has a pumping length (traditionally m), and you have to divide your string into three substrings x y z such that all of the following are true: 1. |y| > 0 2. |xz| < m 3. x y^n z remains in the language for all n. Condition (2) prevents us from using the maweki strategy.

thaumasiotes 5y ago

Just to tie everything up, if you have Dirichlet's theorem it's easy to show that {1^x: x not prime} is irregular through a "direct" proof by contradiction using the pumping lemma. 1. Assuming the language is regular, the pumping lemma tells us that it has a pumping length m, and all strings of length at least m can be divided into a prefix x, a suffix z, and a pumpable substring y, such that: 1a. |xz| < m 1b. |y| > 1 1c. The concatenation x y^n z remains in the language for all n. (In this case, this means that |xz| + n*|y| is nonprime for all nonnegative y.) 2. Consider the string c = 1^p², where p is a prime number greater than m[1]. 3. The pumping lemma will divide c into substrings x y z as described above. 4. Observe that |xz| < m < p and |y| = p² - |xz| 5. Dirichlet's theorem tells us that the arithmetic sequence {a + nd} contains infinitely many primes as long as a and d are coprime. Pumping our string c will generate strings with lengths belonging to the arithmetic sequence {|xz| + n(p² - |xz|)}. It remains to be shown that |xz| and (p² - |xz|) are coprime. 6. Observe that any number which divides both (p² - |xz|) and |xz| will also divide [(p² - |xz|) + |xz|] = p². 7. Since p is prime, the only divisors of p² are 1, p, and p². 8. Since |xz| < p, we can see that gcd(|xz|, (p² - |xz|)) = 1. This completes the proof; pumping c is guaranteed to produce not just one but infinitely many strings of prime length. [1] Euclid tells us that there is no greatest prime number, so we can guarantee the existence of such a p.