While I definitely understand your first issue, I once read somewhere (might be Lee Smolin's book 'The Trouble With Physics') something along the lines of "If you have any physical theory, there are going to be practical ways to test it. Find them.'I must say I quite strongly believe in that statement.

@JHI There is a difference between being falsifiable and being falsified.

Any proof I feel I don't understand? How about well over 95% of all proofs I read..

My first idea would be to simply use induction. Maybe first on $k$ and then on $|A_k|$. Can anyone convince me this is bound to fail?

Idea: prove that we may assume there exists at least k mutually coprime integers and invoke CRT.

According to 'On the largest prime factor of the Mersenne Numbers', written by Ford, Luca, and Shparlinski, Schinzel proves in 'On primitive prime factors of $a^n - b^n$' that the largest prime factor of $2^n-1$ is at least $2n-1$ for all $n \ge 13$.

No, I am not correct. This conjecture has been proven by Maier and Tenenbaum in in their 1984 paper 'on the set of divisors of an integer', which was published in Invent. Math.

It is an old conjecture from Erdös (that is, afaik, still open) that almost all integers $n$ have two divisors $d_1$ and $d_2$ with $d_1 < d_2 < 2d_1$.

If I remember correctly, Erdös himself was positive that this construction can't be improved easily (he called it hopeless even), which is the reason he offered a large prize for it.

My guess would be that tightening the $o(1)$ has more to do with understanding $L(k)$, than understanding this particular problem. It seems (to me) more exciting to try to get bounds on $a,b$ directly in terms of $L(k)$.

The product of the primes between $n/2$ and $n$ is of magnitude $e^{(1/2+o(1))k}$. So this gives $a+b=e^{(1/2+o(1))k}$, right? Or am I misunderstanding the algorithm?

Small quibble: $L(k)$ is not really asymptotic to $e^k$. However, $L(k) = e^{(1 + o(1))k}$ is true.

@Mark, When I read 'the number of integers involved in a solution of $x + y = n$ for a fixed $n$ will have zero relative density in the entire set' I thought 'well, that's trivial, because that number is finite for every fixed $n$, while the entire set is infinite. But that does't mean you can remove these for infinitely many $n$.' But after some thought I realized that you probably mean that, if $A_1(n)$ is the number of solutions to $x + y = n$, then $\displaystyle \lim_{n \rightarrow \infty} \frac{A_1(n)}{A(n)} = 0$ with high probability, right?