nt.number theory - Smallest k-term AP of primes

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)#$. It is easy to show that $n#>n$, and hence we get the lower bound

$$S(k)>(k-1)^2$$
Let $l=lfloor log_2(k-1)rfloor$. Then it is slightly harder (e.g. see http://godplaysdice.blogspot.com/2007/09/hand-waving-asymptotics-of-primorial.html) to show that
$$(k-1)#>frac{(k-1)^l}{2^{l(l+1)/2}}$$

This gives us

$$S(k)>frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2}$$
I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

You can regain your original $prod_{p_ileq k}p_i$ if you can rule out the possibility that the AP can start with $k$ itself, and this then gives you a lower bound

$$S(k)>(k-1)k^{(l-1)/2}$$
where $l=lfloorlog_2krfloor$.

Update: Of course, you can also gain a slight improvement by noting that the first term of the AP must be at least k, and hence

$$S(k)>k+(k-1)^{(l+1)/2}$$
since if we write our AP as $a,a+q,...,a+(k-1)q$then we're trying to find a lower bound for $a+(k-1)q$. This combines our best known bounds for both $a$ and $q$. I suspect that asymptotically $q$ will behave like $k#$, and so the $e^k$ is best possible, and the $(k-1)$ factor is fixed, so any improvements must come from better lower bounds for $a$, but these would be negligible compared to $e^k$. In summary, I think your given lower bound is essentially best possible.

• Next gr.group theory - Does a Cayley graph on a minimal symmetric set of generators determine a finite group up to isomorphism?
• Previous linear algebra - Slick proof?: A vector space has the same dimension as its dual if and only if it is finite dimensional