My apologies, I'm quite new to cryptography.
If we relax the definition of perfect secrecy such that for cyphertext $c$, messages $m_0$ and $m_1$, and constant $E$:
$P[c|m_0] \le E * P[c|m_1]$
Using this, Can I prove a lower bound on the size of the key space as a function of the size of the message space?
I don't understand how I can know anything about the size of the key space without further knowledge of the encryption procedure used and the size of messages and keys.
Oddly enough, if the equation holds for any $m_0, m_1$ of the appropriate length, it would appear that relaxing this requirement doesn't allow us to shrink the key size at all (!). That is, the key size must still be as long as the plaintext size (or, more precisely, there must be at least as many possible keys are there plaintexts). Allowing a value of $E > 1$ turns out not to allow us to use smaller keys; OTP is still an optimal solution for the requirement.
Here's why: this requirements still requires plaintext $m_1$ to have nonzero probability (as if it doesn't, then the equation can't hold if $m_0$ is any plausible plaintext). Any, if there were fewer keys then plaintexts, that would mean that some plaintext is impossible (and hence have zero probability). Because that can't happen, that means that there must be at least as many keys as plaintexts.
