How could this be $E=-\nabla\varphi-\frac{\partial A}{\partial t}$? I know how to derive the formula, but, in view of freedom, the left hand side $E$ has 3 components while the right hand side provides 1 constraint from $\varphi$ and 3 from $A$. I mean, why does a 3 variables unknown vector needs 4 constraints to determine? Is there any abundance or dependence? 
And I have no idea what the relevant theorems about connection between solutions of equations and freedom are? (Does "freedom" mean number of unknown variables minus constraints or equations?)
Let me put it another way, in physics, $E$ is uniquely determined by two potentials, namely scalar $\varphi$ and vector $A$. But why do we need 4 components to determine only 3 unknowns?
 A: A better way to look at this is that the four potential $A$ gives the Faraday by exterior differentiation in $\mathbb{R}^4$; $dF=A$. Then the sources are coupled to the Hodge dual by $d *F = \mu_o *J$ where $J$ is the four-current. In particular, $A = \phi dt + \omega_{\vec{A}}$ and $J = \rho dt+ \omega_{\vec{J}}$ and $\omega_{\vec{F}} = F_1dx+F_2dy+F_3dz$ is the work-form correspondence of vectors and forms. Here I denote $\rho = dQ/dV$ the charge-density and $\phi$ the electric potential and $\vec{A}$ the vector potential. The exterior derivatives above encode the curl and divergence since:
$$ d \omega_{\vec{F}} = dt \wedge \frac{\partial \vec{F}}{\partial t}+\Phi_{\nabla \times \vec{F}} $$
and $\Phi_{\vec{F}} = F_1 dy \wedge dz+F_2dz \wedge dx+F_3 dx \wedge dy $. Or, more to the point:
$$ F=dA = d\phi \wedge dt + \Phi_{\nabla \times \vec{A}} = \omega_{\nabla \phi} \wedge dt +dt \wedge \frac{\partial \vec{A}}{\partial t}+ \Phi_{\nabla \times \vec{A}} = -dt \wedge \omega_{\vec{E}}+\Phi_{\vec{B}}$$
I might be off by a sign in what follows, but basically the Hodge dual flips work and flux forms
$$ *F= -dt \wedge \omega_{\vec{B}}+\Phi_{\vec{E}} $$
and so $d*F = \mu_o *J$ gives a curl and divergence for $\vec{E}$ and $\vec{B}$ whereas the $dF=0$ gives a curl and divergence for the $\vec{B}$ and $\vec{E}$. These four equations are of course Maxwell's Equations. The asymmetry between the equations is an experimental fact (so far as we know) there is no magnetic charge. Look up "complexion" in Misner Thorne and Wheeler for more on how the equations modify in the presence of magnetic charge and current.
Ok, so let's do some counting in view of all this. We have 6 functions of spacetime which are coupled under Maxwell's Equations. These are $E_1,E_2,E_3,B_1,B_2,B_3$. These are derived from the four-potential which has 4 functions of spacetime; $\phi, A_1,A_2,A_3$. Even so, there is freedom in the choice of the potential. The choice of gauge allows us to shift $A$ by $dg$ since $d(A+dg)=dA$ so $A+dg$ generates the same physical fields (ignoring Aharanov Bohm...).
In any event, I don't think it's right to think of $\vec{E}$ and $\vec{B}$ as independent variables. They're not. We must respect Maxwell's Equations so they're coupled and when you write the potential and vector potential you fix both the electric and magnetic field.
Perhaps there is something to your question, but I don't understand it yet.
