Density of P-complete languages Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$.  Let $L_n$ be the number of strings in $L$ with length $n$.  For a function $d(n)$ from the positive integers to the positive real numbers, $L$ has upper density $d(n)$ if $L_n \le 2^n d(n)$ for all sufficiently large $n$.


  Do any P-complete Boolean languages have upper density $O(1/n)$?


Motivation


PARITY has upper density $1/2$.  YES (the language of all finite binary strings) has upper density 1.  Any finite language has upper density 0.
A sparse language $L$ has the property that there is a polynomial $p(n)$ such that $L_n - L_{n-1} \le p(n)$ for all $n$.  If $L$ is a sparse language, then $L_n \le p_1(n)$ for a polynomial $p_1$ of degree one greater than that of $p$, so the upper density of $L$ is zero.
Jin-Yi Cai and D. Sivakumar showed that a P-complete language cannot be sparse unless P = L (= LOGSPACE).  Since P=co-P, any language of which the complement is sparse cannot be P-complete either, unless P=L.
By a simple inequality (see e.g. Corollary 2 of Rosser and Schoenfeld 1962), PRIMES has upper density $(\log_2 e)/n$.  Question Are the problems PRIMES, FACTORING known to be P-hard? discusses whether PRIMES is P-hard (this seems to be open currently).
In some sense, the complete (or universal)languages for a complexity class contain all the structure of the class.  So my tentative hypothesis, based on a wild extrapolation of Cai and Sivakumar's result, would be that such languages cannot be too sparse.  The usual polynomial bound defining sparse languages seems too restrictive, so I'm asking about a bound that is a little less restrictive.


The work on lowness by Fortnow, Hemaspaandra, and others is also possibly related.

The question can be asked of classes other than P, but I can't recall any results that would allow establishing density of, say, $k$-SAT.  Pointers to relevant literature would be most welcome.

Acknowledgements

See also related question Conditional density of primes.  Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.
I don't know what the density of common P-complete problems is, but here is a padding argument that shows how to lower any density below $1/n$:

Take your favorite P-complete language $L_n \subseteq \{0,1\}^n$. This language has some density $d(n) \in \omega(1/n)$. Now define $L&#39;_{n + m} = \{x0^m | x \in L_n\}$. In general, $m$ will be some function of $n$, so this might not define $L&#39;$ for all sizes, since we are worried only about the upper density, just make $L&#39;_k = \emptyset$ if $k \neq n + m$. What is the upper density of $L&#39;$? Well, we have 

\[
d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m}
\] 

Now lets use LOG-reductions to build a machine $M$ for $L$ using a machine $M&#39;$ for $L&#39;$. Well, if you are given an input $x$ then simply copy it one bit at a time to the query tape (also use a counter to count what $n$ is), then use a second counter to count upto $m(n)$, adding one every time you add a zero to the query tape (to have log space, we need $m(n) \in poly(n)$ and easily computable). Then query and return the output as your answer.

If we want to be sure we are smaller than $1/n$ then just pick $m(n) = n$, and then we will have $d&#39;(2n) \leq d(n)/2^n \in O(1/n)$.