\section{Introduction}
\label{sec 1}

The biological functions of the highly negatively charged DNA are intimately coupled to the positive counterions that neutralize them (for a review see Refs. \ \onlinecite {Kornyshev2007,Cherstvy2011}). A particularly significant effect ubiquitous in biological environment is the {\em DNA condensation} in multivalent salt DNA solutions \cite{Rau246 92,Rau260 92,Pelta BJ96,Pelta JBC96,Plum88,Raspaud99}. In this case the presence of a multivalent ion atmosphere creates effective {\em attractive interactions} between nominally equally charged DNA molecules that can lead to toroidal aggregate formation, which seems to be the preferred morphology for high-density packaging of DNA \cite{Hud2005}. In fact, most vertebrate sperm cells contain DNA toroidal aggregates, each measuring about 100 nm in outside diameter, condensed by arginine-rich and thus highly charged proteins. Condensed DNA  aggregates seem to be relevant also for gene packing in bacteriophages and for their potential impact in artificial gene delivery \cite{Rudi2008}. While DNA condensation is also at least in part due to electrostatic interactions, it can not be explained within the mean-field Poisson-Boltzmann imagery \cite{Rudi2010}. A radical reformulation of the theory of electrostatic interactions is needed, based on the concept of "strong coupling" between the multivalent salt counterions and the charges on the DNA backbone, in order to understand the counterintuitive change in sign of electrostatic interactions between nominally equally charged bodies \cite{Rudibook}. While the general framework of the strong-coupling effects is well understood, there are different ways of its exact implementation that accentuate different facets of the interaction between the DNA backbone and the mobile multivalent ions in the bathing solution \cite{Cherstvy2011,Teif}. In order to elucidate and eventually differentiate between different theoretical approaches more detailed experiments on the effects of multivalent ions are needed. While the investigation of equilibrium properties of multivalent counterion DNA solutions are vigorously pursued \cite{Rau246 92,Rau260 92,Pelta BJ96,Pelta JBC96,Plum88,Raspaud99}, the concomitant elucidation of their dynamical properties leaves a lot to be desired.

Dynamics of multivalent counterions would be in particular interesting to probe in order to reveal otherwise inaccessible features of the strong-coupling attractive interactions between DNA molecules \cite{Rudi2010}. However, not all multivalent ions in DNA solutions act the same and they are clearly differentiated in the way they affect the ds-DNA. Early light-scattering studies indicated that DNA collapse into compact structures occurs when $\approx90\%$ of the DNA phosphate charges are neutralized by condensed counterions \cite{Wilson79}. It also became clear that in fact very few cations induce ds-DNA condensation. Univalent and divalent cations, excluding transition-metal ions such as Mn$^{2+}$, Ni$^{2+}$, and Cu$^{2+}$  \cite{Hud2001}, do not condense ds-DNA even when present at very high concentrations, while almost all divalent cations condense the single-stranded DNA but not the ds-DNA.  On the other hand, alkaline-earth divalent cations, such as Mg$^{2+}$, Ba$^{2+}$ and Ca$^{2+}$, do condense triple stranded DNA with a more highly charged helix than the ds-DNA form, but not the ds-DNA \cite{Qiu2010}. Furthermore, counterions Mn$^{2+}$, Cd$^{2+}$, Co(NH$_3$)$^{3+}$, polyamines such as spermidine$^{3+}$, spermine$^{4+}$, polylysine$^{+}$, etc. do condense ds-DNA at finite concentrations. While electrostatics without doubt plays an important role in the DNA condensation mechanism \cite{Cherstvy2011}, it cannot be the sole factor affecting it as, e.g., Co(NH$_3$)$^{3+}$ is more efficient in condensing DNA than spermidine$^{3+}$, both being trivalent counterions. The best condensing agents appear to be those that bind into one of the DNA grooves \cite{best}. Based on these varied properties of multivalent counterions, it is thus clear that their dynamical behavior could provide an additional clue to the puzzles posed by DNA collapse.

In what follows, we thus plan to investigate the dynamics of multivalent counterions by using the dielectric spectroscopy (DS) to study DNA solutions at various DNA densities and salt content. DS \cite{Buchner2009} has been successfully used to probe the dynamics of aqueous polyelectrolyte solutions \cite{Nandi, Bordi2004}. The higher-frequency dielectric response located in high MHz-GHz region (near 17 GHz) is usually associated with the macromolecular hydration and the bulk dielectric response of water \cite{Hastedbook}.  On the other hand, the lower-frequency modes (between 100 Hz and 100 MHz) are dominated by the counterion atmosphere around each polyelectrolyte and this fluctuating charge cloud responds to the applied electric field \cite {Bordi2004}. We recently resolved the counterion response to external fields into two fundamental dissipative peaks that appear as fingerprints of two relaxation modes arising from the diffusive motion of counterions \cite{DNAPRL06, PRE2007, DNAEPL, Vuletic2010}: the dynamics of free diffuse counterions detected in the MHz frequency range probes collective properties of the polyelectrolyte solution, whereas the dynamics of condensed counterions in the kHz range probes the single-chain polyelectrolyte properties. It is noteworthy that on the latter time scale the polarization of counterions happen along an essentially stationary DNA chain. We have shown that the details of the counterion dielectric response depend on various parameters characterizing the polyelectrolyte chain and the polyelectrolyte solution as a whole, such as the length of the polyelectrolyte chain, its charge density and flexibility, and the concentration of polyelectrolyte chains, as well as the ionic strength of the added salt.

DNA has been studied by DS since the early 1960s \cite {Sakamoto76, Mandel77, Bordi2004}. In the case of univalent cations such as Na$^{1+}$, the MHz relaxation in the semidilute regime of DNA solutions corresponds to the collective (de Gennes--Pfeuty--Dobrynin) correlation length as the defining property. This is true for DNA as well as for other polyelectrolytes, e.g., hyaluronic acid \cite{Vuletic2010}. Since the DS technique can be applied at very low polyelectrolyte concentrations, even below 10 g/L, it can be seen as complementing scattering techniques, such as SAXS and SANS, that are usually applicable only for much higher polyelectrolyte solution concentrations \cite{TomicMacromolecules}. Recent experiments by Salomon {\it et al.} \cite{VuleticMacromolecules2013} showed that the characteristic length scale probed in SAXS measurements corresponds to the characteristic length scale of the HF dielectric relaxation obtained by DS, thus confirming that both techniques probe the same correlation length of the semidilute DNA solutions. The specific features of DNA, not observed for other polyelectrolytes, are pronounced flexibility of short double-stranded DNA (ds-DNA) fragments \cite{DNAEPL,Yuan2008, Lee2010} and locally fluctuating regions of exposed hydrophobic cores of long DNA \cite{PRE2007}. The latter can be associated with the nucleation of DNA denaturation bubbles stemming from broken segments of several consecutive base pairs \cite{bubbles}. The kHz relaxation, on the other hand, reveals the single molecule properties such as the flexibility of a single DNA chain as described by its persistence length. Its variation with the solution electrostatic screening (Debye) length can be rationalized by the Odijk-Skolnick-Fixman (OSF) theory, applicable to rigid and semi flexible chains \cite{Odijk, Fixman}.

In order to shed additional light on the behavior of ds-DNA in solutions of polyvalent salts we thus embark on a systematic study of the dielectric response of DNA solutions in multivalent salt bathing solutions. As a point of departure we choose the Mg$^{2+}$ cation. Our choice is based on the fact, {\sl vide supra}, that Mg$^{2+}$ does not induce any DNA condensation but nevertheless still affects DNA solution dynamics through enhanced screening, as will become evident as we proceed. This differentiation between the condensation effects and the screening effects is important in order to keep a clear track of the specificities of the multivalent ions. In subsequent studies we plan to move from the predominant screening effects to more complicated condensation effects as present with Mn$^{2+}$ or Co(NH$_3$)$^{3+}$ ions, elucidating their interrelation and prevalence.  Consistent with our previously elaborated methodology, we will probe the two dielectric response modes involving counterions in DNA solutions and attempt to rationalize our findings within the conceptual framework elaborated for the case of univalent salt DNA solutions and adapted specifically to the case of multivalent counterions.

\section{Materials and methods}
\label{sec2}

Salmon testes lyophilized Na-DNA threads were purchased from Sigma-Aldrich. Previous gel electrophoresis measurements showed that the majority of DNA fragments were in the 2--20 kbp range, so that the estimated average DNA fragments were 4 $\mu$m long \cite{PhysicaB2012}. As for the Na-DNA solutions we were always in the semidilute regime \cite{PRE2007}. A crude estimate based on the de Gennes arguments gives the chain overlap concentration $ c^\ast$ of the order of 0.001 g/L, which is one order of magnitude below the lowest concentration found in our experiments and even if we take into account the shortest chains in our DNA solutions we estimate that $ c^\ast \approx 0.007$ g/L, which is still lower than the lowest concentration of DNA solutions in our measurements \cite{deGennes76, note1}.

First we prepared the Mg$^{2+}$ salt of DNA in pure water and in solutions with added MgCl$_2$  salt. The reason for this is that we want to study DNA aqueous solutions containing only magnesium cations in order to avoid possible complications due to the presence of sodium cations \cite{Lyons64}. Thus Mg-DNA pure water solutions within concentration range $0.01$ g/L $\leq c \leq 4$ g/L were prepared by exhaustive dialysis according to the protocol as described in Ref. \ \onlinecite{noteprotokol1}. Then DNA solutions with different added salt ionic strengths were made. MgCl$_2$ was added to Mg-DNA water solution with a concentration chosen in such a way as to have the added salt ionic strength in the range $\text{0.003 mM} \leq I_{\mathrm{s}}\leq \text{4 mM}$ \cite{note2}. In addition, Mg-DNA solutions with concentrations in the range $\text{0.01 g/L}\leq c \leq \text{4 g/L}$ and with the added salt ionic strength $I_{\mathrm{s}}=$~0.3 mM and $I_{\mathrm{s}}=$~3 mM were prepared \cite{noteprotokol2}. Finally, and for the sake of comparison, Na-DNA solutions in the presence of a MgCl$_2$  buffer were also made according to protocols as above.

UV spectrophotometry measurements of the DNA absorbance intensity at 260 nm were done in order to verify the nominal DNA concentration. The concentration was then determined assuming double-stranded conformation, implying the extinction coefficient at 260 nm equal to 20 L/gcm. The measured concentrations for DNA solutions in 1 mM of added salt were consistently smaller by about 20\% than the nominal ones, as found before \cite{ PRE2007}. This difference is due to water content not taken into account by the spectrophotometry approach. Throughout this paper we refer to these measured concentrations as the {\em DNA concentrations}. We have also used UV spectrophotometry in order to verify the stability of the double-stranded conformation of Mg-DNA solutions. The obtained data clearly showed that the ds conformation was fully preserved not only in added salt, but also in the pure water solutions in the whole range of studied concentrations (Fig.\ \ref{fig1}).

\begin{figure}
\resizebox{0.43\textwidth}{!}{\includegraphics*{fig1.eps}}
\caption{Normalized absorption ($A/l$, where $l$ is the light path length) of Mg-DNA pure water solutions (open circles) and of Mg-DNA solutions with added salt MgCl$_2$, $I_{\mathrm{s}} = 0.3$ mM (full circles) as a function of DNA concentration. Inset: extinction coefficient versus Mg-DNA concentration indicating double-stranded conformation in the whole concentration range.}
\label{fig1}
\end{figure}

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig2.eps}}
\caption{Imaginary ($\varepsilon^{\prime\prime}$) and real ($\varepsilon^\prime$) part of the dielectric function at $T=25^\circ$C of (a),(b) pure water Mg-DNA solutions and (c),(d) Mg-DNA solutions with added salt MgCl$_2$, $I_{\mathrm{s}}= 0.3$ mM for representative a1--a3 (4, 0.5, 0.022 g/L) and b1--b3 (2, 0.4, 0.08 g/L) DNA concentrations. The full lines are fits to the sum of the two Cole-Cole forms; the dashed lines represent a single CC form.}
\label{fig2}
\end{figure}

Dielectric spectroscopy measurements were performed at room temperature (25$^\circ$C) using a setup which consisted of a home made capacitive chamber with parallel platinum electrodes and a temperature control unit, in conjunction with the Agilent 4294A precision impedance analyzer operating in $\nu= 40$~Hz--110 MHz frequency range. The capacitive chamber enables reliable complex admittance measurements with reproducibility of 1.5\% of samples in solution with small volume of 100 $\mu$L and with conductivities in the range 1.5--2000 $\mu$S/cm. The chamber constant value is $l/S = 0.1042\pm 0.0008$~cm$^{-1}$, where $S = 0.98$~cm$^{2}$  is the effective electrode cross section corresponding to the sample of 100 $\mu$L and $l = 0.1021\pm 0.0001$~cm is the distance between the electrodes. Extrinsic effects, especially those due to free ions and electrode polarization, were removed by using the reference subtraction method. To this end, MgCl$_2$ solutions of different molarities were chosen for reference samples and measured in addition to DNA samples. This method gives reliable results up to the concentration of 2 g/L. At higher concentrations the influence of electrode polarization is sufficiently large both due to counterions and added salt ions, so that it cannot be subtracted in a satisfactory way. Because of that we were only able to determine the parameters of the high-frequency relaxation for concentrations below 2 g/L. Detailed measurement procedure and data analysis was given previously \cite{PRE2007, PhysicaB2012}. Since then an additional improvement in the data analysis has been implemented. In our previous method, the most time-consuming and difficult to automate task was finding the appropriate electrolyte solution to be used as a reference: simple algorithmic matching in most cases requires an additional manual adjustment. With this in mind we have written a custom fitting program in Python using the open source Enthought Tool Suite (Traits, TraitsUI, Chaco). It provides interactive visualization and matching of the background to sample spectra. Model fitting can then be applied immediately to the resulting dielectric spectra. In the case of two overlapping dielectric modes near the high-frequency limit of our experimental window, we additionally rely on fitting the model to the real part of conductivity. In particular, this improves the accuracy of the extracted mode width.

\section{Results}
\label{sec3}

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig3.eps}}
\caption{Dielectric strength ($\Delta\varepsilon$, upper panel) and mean relaxation time ($\tau_0$, lower panel) of Mg-DNA pure water solutions as a function of DNA concentration. Open circles and triangles stand for the HF and LF mode, respectively.}
\label{fig3}
\end{figure}

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig4.eps}}
\caption{Dielectric strength ($\Delta\varepsilon$, upper panel) and mean relaxation time ($\tau_0$, lower panel) of Mg-DNA water solutions with added salt MgCl$_2$; $I_{\mathrm{s}} = 0.3$ mM as a function of DNA concentration. Full circles and triangles stand for the HF and LF mode, respectively.}
\label{fig4}
\end{figure}

Figure \ref{fig2} shows representative spectra for Mg-DNA pure water solutions and for solutions with 0.1 mM added salt. The complex dielectric spectra can be described by the sum of the two Cole-Cole functions
\begin{equation}
\varepsilon(\omega)-\varepsilon_\infty
 = \frac{\Delta\varepsilon_{\mathrm{LF}}}{1 + \left(i \omega \tau_{0,\mathrm{LF}} \right)^{ 1-\alpha_{\mathrm{LF}} }}
 + \frac{\Delta\varepsilon_{\mathrm{HF}}}{1 + \left(i \omega \tau_{0,\mathrm{HF}} \right)^{ 1-\alpha_{\mathrm{HF}}}},
\label{Cole}
\end{equation}

where $\varepsilon_\infty$ is the high-frequency dielectric constant, $\Delta\varepsilon$ is the dielectric strength, $\tau_0$ the mean relaxation time, and $1-\alpha$ the symmetric broadening of the relaxation time distribution function of the low-frequency (LF) and high-frequency (HF) dielectric mode.
The broadening parameter of both modes is typically $1 -\alpha \approx 0.8$.  The concentration dependencies of the dielectric strengths and mean relaxation times for pure water Mg-DNA solutions and solutions with added salt are shown in Fig.\ \ref{fig3} and Fig.\ \ref{fig4}, respectively.

From the measured mean relaxation time $\tau_0$ we first extract the characteristic length scales $L$ along which counterions diffuse following the applied ac electric field. We use the expression $\tau_0 \propto L^2/D_{\mathrm{in}}$, where $D_{\mathrm{in}}$ is the diffusion constant of counterions which is well approximated by the diffusion constant of bulk ions \cite{PRE2007, PhysicaB2012, Angelini2006}. Since we work with Mg-DNA aqueous solutions, we use the diffusion constant of Mg$^{2+}$ ions $D_{\mathrm{in}}=0.706\times 10^{-9}$ m$^2$/s \cite{textbook}.

\subsection{HF mode}
\label{A}

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig5.eps}}
\caption{Characteristic length of the HF mode ($L_{\mathrm{HF}}$) for pure water Mg-DNA solutions (open circles) and for Mg-DNA solutions with added MgCl$_2$ salt; $I_{\mathrm{s}}= 0.3$ mM (full triangles) and 3 mM (full circles) as a function of DNA concentration ($c$). The full line is a fit to the power law $L_{\mathrm{HF}} \propto c^{-0.53\pm0.03}$. The dashed lines stand for the theoretically expected Debye screening lengths for the investigated $I_{\mathrm{s}}$ of added salt.}
\label{fig5}
\end{figure}

Our first important result concerns the characteristic length of the HF mode which probes the collective properties of DNA solutions. For pure water DNA solutions with Mg$^{2+}$  counterions, the characteristic length $L_{\textrm{HF}}$ follows the power law $L_{\textrm{HF}} \propto c^{-0.53\pm0.03}$ in an almost three-decades-wide range of concentration (Fig.\ \ref{fig5}). Thus, in the semidilute solution regime with divalent Mg$^{2+}$ counterions the de Gennes--Pfeuty--Dobrynin (dGPD) correlation length or the mesh size $\xi\propto c^{-0.5}$ \cite{deGennes76, Dobrynin} is revealed as the most relevant length scale. This is in distinction to the univalent Na$^{1+}$ counterions, where the mesh size $\xi$ characterizes the organization of DNA chains only at concentrations larger than 0.5 g/L, whereas at lower concentrations it is replaced by the exposed hydrophobic core scaling $c^{-0.33}$, corresponding to incipient denaturation bubbles \cite{ PRE2007,TomicMacromolecules}. As we  suggested previously, this may reflect the appearance of locally fluctuating denaturation bubbles due to the relatively weak effect of Na$^{1+}$ counterions that are unable to screen the repulsion between two DNA strands at these low concentrations \cite{DNAPRL06, PRE2007}. An increased stability of the double-stranded conformation detected in the case of Mg-DNA can thus be interpreted with diminished repulsion between two DNA strands. Both effects can be associated with the pure screening action of divalent magnesium counterions. These results thus suggest a much enhanced screening effect of magnesium counterions as compared with sodium, eventually yielding an increased stability of the ds conformation of DNA. A very similar conclusion has been reached by Lyons {\it et al.\@}{}\ \cite{Lyons64} on the basis of their counterion activity coefficient data and assuming that binding is basically determined by the long-range electrostatic interactions, with site-specific binding playing only a marginal role. They have also found that the activity coefficient of Mg-DNA was five times smaller than the one for Na-DNA which indicates much stronger binding of magnesium cations to DNA.

With MgCl$_2$ as added salt, the behavior of $L_{\mathrm{HF}}$ remains unchanged (Fig.\ \ref{fig5}), so that again the dGPD correlation length is the only relevant length scale. This remains the case as long as the ionic strength of the Mg-DNA is larger than the ionic strength of the added salt. At lower DNA concentrations, the $L_{\mathrm{HF}}$ clearly levels off, with a limiting value close to the Debye screening length theoretically expected for this salt ionic strength. Qualitatively, this result is similar to the one found previously for Na-DNA water solutions with NaCl as the added salt. However, a significant change is found at the quantitative level indicating again an enhanced screening capability of DNA with Mg$^{2+}$ cations as compared to DNA with Na$^{1+}$ cations. Previously observed results indicate that NaCl added salt with the ionic strength only twice the ionic strength of Na-DNA prevails in the DNA solution screening and promotes the Debye screening length to the fundamental length scale \cite{DNAPRL06, PRE2007}. Conversely, the results displayed in Fig.\ \ref{fig5} show that adding of MgCl$_2$ to an ionic strength of six times the effective value of Mg-DNA is needed to overcome the intrinsic screening of Mg-DNA \cite{note4}.

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig6.eps}}
\caption{Normalized dielectric strength $\Delta\varepsilon /(c\cdot L^2)$ of the HF mode (open circles) and of the LF mode (open triangles) as a function of DNA  concentration $c$ for pure water Mg-DNA solutions. The dashed lines are guides for the eye.}
\label{fig6}
\end{figure}

Finally, our data enable an estimate of the number $f$ of oscillating counterions which is given by $\Delta\varepsilon/(c\cdot L^2)$ \cite{PRE2007}. Increasing DNA concentration leaves the fraction of free counterions participating in the HF relaxation process unchanged (Fig.\ \ref{fig6}); that is, it features qualitatively similar, concentration-independent $f$ as found for Na-DNA \cite{PRE2007}. This result validates the standard theoretical models which use the Manning-based definition of $f$ as the concentration-independent parameter.

\subsection{LF mode}
\label{B}

The second important result concerns the LF mode which characterizes the single-chain properties. As for Na-DNA, we find the characteristic length scale $L_{\textrm{LF}} \propto c^{-0.23\pm0.02}$ to behave as predicted for a Gaussian chain composed of correlations blobs, that is $L_{\textrm{LF}} \propto c^{-0.25}$ (Fig.\ \ref{fig7}). However, in Mg-DNA this characteristic length scale is shorter by about 1.5 times than in the Na-DNA \cite{DNAPRL06, PRE2007}, an effect which can again be ascribed to the enhanced screening in Mg-DNA. This result is also in accord with the viscosity data which show that Mg-DNA is hydrodynamically shorter than Na-DNA \cite{Lyons64}. The enhanced screening in Mg-DNA is also reflected in an effective number of condensed counterions participating in the LF relaxation (Fig.\ \ref{fig6}) which, in contrast to the Na-DNA \cite{PRE2007}, decreases with an increase in DNA concentration. The latter result indicates that the concentration-independent Manning-based definition for the number of oscillating counterions is not valid in this case. A rather surprising result in comparison to Na-DNA data is then obtained in the presence of added MgCl$_2$ salt with  $I_{\mathrm{s}}= 0.3$ mM (Fig.\ \ref{fig7}). In this case, $L_{\textrm{LF}}$ stays approximately constant in the whole measured concentration range at the level of  $L_0 = 50$ nm, which suggests that in this regime $L_{\textrm{LF}}$ is proportional to the structural persistence length of DNA.

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig7.eps}}
\caption{Characteristic length of the LF mode ($L_{\textrm{LF}}$)  for pure water Mg-DNA solutions (open triangles) and for DNA solutions with added MgCl$_2$ salt; $I_{\mathrm{s}}= 0.3$ mM (full triangles) as a function of DNA concentration ($c$). The full line is a fit to the power law $L_{\textrm{LF}} \propto c^{-0.23\pm0.02}$. The dashed line designates theoretically expected value for DNA structural persistence length $L_0 = 50$ nm.}
\label{fig7}
\end{figure}

The dependence of $L_{\textrm{LF}}$ on the added salt ionic strength $I_{\mathrm{s}}$  is shown in Fig.\ \ref{fig8} for two selected Mg-DNA concentrations. The observed data follow the OSF behavior $L_p = L_0 + a \cdot I_{\mathrm{s}}^{-1}$, where $L_0$ is DNA structural persistence length and $a$  is the effective charge density of DNA \cite{Odijk, Fixman}. From the fit to the OSF expression we get $L_0 = 57\pm5$ nm and $a = 4.4\pm1.2 $nm$\,$mM \cite{note3}. While the value of $L_0$ close to $50$ nm is in accordance with standard expectations as well as experimental results for DNA structual persistence length \cite{Bloomfield00, Baumann97}, the value of the coefficient $a$ which describes the effective linear charge density is two times smaller than the value found in Na-DNA. A qualitatively similar result has been previously found by a magnetic birifrigence experiment \cite{MaretWeil}.
It is noteworthy that both values of the coefficient $a$ are much smaller than the value expected by the standard OSF theory $a=\frac{\alpha^2}{z^2}32.4$ nm$\,$mM, where $\alpha$ is the degree of ionisation, $z$ is counterion valency \cite{note3}. There could be several reasons for this type of discrepancy, quite probably based on the limitations inherent in the OSF theory itself that completely disregards any ion-specific effects \cite{Ben-Yaakov2011}. Ion specificity is a compound effect and has many potential sources including polarizability, London-dispersion effects, and other nonpolar interactions that could play a significant role also in ion-DNA interactions \cite{Misra95}. While these effects can modify the ion-DNA interaction they are as a rule long range and cannot be viewed as short-range tight binding of ions to specific sites along the DNA.

\begin{figure}
\resizebox{0.48\textwidth}{!}{\includegraphics*{fig8.eps}}
\caption{
Characteristic length of the LF mode ($L_{\textrm{LF}}$) for DNA solutions with varying added salt ($I_{\mathrm{s}}$) for two representative DNA concentrations: $c=0.04$~g/L (stars); $c=0.4$~g/L (diamonds). The full line is a fit to the expression $L_p = L_0 + a \cdot I_{\mathrm{s}}^{-1}$ with $L_0 = 57\pm5$~nm and $a =  4.4\pm1.2$~nm~mM.
}
\label{fig8}
\end{figure}

Figure \ref{fig8} also attests to the respective roles of intrinsic DNA counterions and ions from the added salt in ionic screening. As in the case of Na-DNA, the OSF model applies as long as the ionic strength of added salt is larger than the ionic strength pertaining to DNA. In the opposite limit the OSF behavior is replaced by the DNA self-screening. Again, comparing with the Na-DNA case,  an important quantitative difference is detected indicating that ten times stronger ionic strength of added salt is needed for Mg-DNA as compared to Na-DNA in order for the OSF behavior to prevail. The data for $c = 0.04$ and 0.4 g/L deviate from the OSF behavior for $I_{\mathrm{s}} < 0.01$~mM and for $I_{\mathrm{s}}< 0.1$ mM, respectively. At these low added salt values $I_{\mathrm{s}} < 0.04 I_{\text{Mg-DNA}}$, where $I_{\text{Mg-DNA}}=4c$ \cite{note4}, the intrinsic counterions become dominant in determining the behavior of $L_{\textrm{LF}}$ and indeed it attains the same value as in pure water Mg-DNA solutions (Fig.\ \ref{fig8}). On the other hand, Na-DNA experiments \cite{PRE2007} show that deviation from the OSF behavior takes place when $I_{\mathrm{s}} < 0.4 I_\text{Na-DNA}$, where $I_\text{Na-DNA}=3c$. In the case of divalent Mg counterions it thus appears that the screening from DNA and its counterions largely overpowers the screening effects of added salt, thus promoting the average size of the chain, as opposed to the OSF persistence length, to the fundamental length scale.

\section{Discussion}
 \label{sec4}

It is important to note that our experiments were performed in the absence of any other kind of cation except Mg$^{2+}$. This presents an important point and allows for a straightforward interpretation when comparing our data with other published qualitatively similar results on DNA with magnesium cations (see \cite{Lyons64} and references therein). Specifically, a shorter statistical end-to-end distance was found by Foerster resonance energy transfer (FRET) experiments for the single-stranded DNA \cite{Chen2012}. In addition, the FRET measurements also showed that Mg$^{2+}$ is even 20--40 times more efficient in screening than Na$^{1+}$ in the case of single-stranded DNA. In a previous DS investigation, Na-DNA solutions with concentration 0.25 g/L were studied in the presence of different amounts of MgCl$_2$ so that the effects of increasing ratio Mg$^{2+}$/base pair were tracked \cite{Bonincontro2002}. Owing to the restricted frequency range in that work, only the dielectric relaxation in MHz range (that is HF) was detected. The data showed an increase of the correlation length $\xi$ and a decrease of the number of oscillating counterions $\Delta\varepsilon_{\textrm{HF}}/(c \cdot \xi^2)$ with increasing ratio Mg$^{2+}$/base pair. The authors of that study suggested that their results might be understood as a consequence of a strong site-binding of Mg$^{2+}$ so that they could not contribute to the dielectric relaxation \cite{Clement73}.  However, these DS data showing larger values of the correlation length for larger amounts of Mg$^{2+}$ ions can be easily understood within a framework where both sodium and magnesium cations can respond equally to applied ac electric fields. Namely, at the low Na-DNA concentration used in that work, the correlation length is short if compared with pure Mg-DNA due to the prevailing hydrophobic scaling with exponent 0.33 instead of the dGPD mesh size scaling with exponent 0.5. Evidently the increasing Mg$^{2+}$ content leads to a larger screening thus yielding larger values of the correlation length. Indeed, we have verified this scenario in our experiments on Na-DNA solutions with MgCl$_2$ added salt. Site-specific binding to DNA was also excluded by Raman data which indicated relatively weak interactions of Mg$^{2+}$ as well as of Na$^{1+}$  with both base and phosphate sites \cite{Duguid93}.
Thus we are lead to conclude that the magnesium counterions interact with DNA prevalently via long-range electrostatic forces and that they respond to applied ac fields in the same way as the sodium cations.

\section{Conclusion}
\label{sec5}

In conclusion, we have analyzed the behavior of magnesium counterions in ds-DNA semidilute solutions by means of dielectric spectroscopy measurements. Our results demonstrate that divalent magnesium cations significantly contribute to the DNA self-screening of  electrostatic interactions. Their screening efficiency is in fact anomalously large when compared to univalent sodium cation standard. However, with magnesium counterions there is as yet no net attraction between DNA segments that would be capable of inducing the full DNA collapse. Other types of multivalent counterions will be studied in order to probe these effects.

As follows from our DS experiments, the effect of magnesium cations on the properties of DNA solutions can be characterized by a shortening of the statistical end-to-end distance of the DNA chains and a smaller effective linear charge density than for the Na-DNA, a clear indication of an ion-specific effect. The magnesium cations also assure the stability of the double-stranded conformation even in the limit of low DNA and added salt concentration by making the dGPD solution correlation length the most relevant fundamental length scale that describes the structural organization of DNA chains in solution. We also find that specific-site short-range strong counterion binding, sometimes assumed to be relevant for DNA counterion interaction, appears to not be particularly relevant for the interaction of magnesium cations with DNA in the studied concentration range of DNA and added salt. On the contrary, we confirm that the counterion-DNA interaction is primarily due to long-range electrostatic forces acting in a similar fashion as in the case of sodium counterions.  Further characterization of a denatured state of DNA in the presence of magnesium cations and other multivalent counterions is currently on the way.

\section*{Acknowledgments}
ICP-AES was performed by I.\ Ladan at the Croatian National Institute of Public Health. Discussions with T.\ Vuleti\'{c} and D.\ Rau  in the early stage of this work, as well as with  M.\ Tomi\'{c} are acknowledged. This work was supported by the Croatian Ministry of Science, Education and Sports under Grant No. 035-0000000-2836. R.P. acknowledges the financial sup\-port from the Slovene Agency for Research and Development (Grants No. P1-0055 and No. J1-4297).


\section*{Acknowledgemets}
This work was supported by the European Research Council (ERC Starting Grant 'EnTeraPIC', number 280145), by the Alfried Krupp von Bohlen und Halbach Foundation, by Helmholtz International Research School for Teratronics (HIRST), by the Initiative and Networking Fund of the Helmholtz Association, by the Center for Functional Nanostructures (CFN) of the Deutsche Forschungsgemeinschaft (DFG) (project A 4.8), by the DFG Major Research Instrumentation Programme, by the Karlsruhe Nano-Micro Facility (KNMF), by the Karlsruhe School of Optics \& Photonics (KSOP), by the Swiss National Science Foundation (NCCR Nano-Tera, NTF MCOMB), by a Marie Curie IAPP Action and by the DARPA program QuASAR. Samples have been fabricated at the EPFL Center for Micro- and Nanotechnology (CMI).

\section*{Methods}

\subsection*{Experimental setup and ring resonator design.}
The pump for Kerr comb generation is generated by an external-cavity laser (New Focus Velocity Model TLB-6728), a polarization controller (PC) and an erbium-doped fibre amplifier (EDFA) providing an output power of up to 37~dBm, see Fig.~\ref{Fig2}. The coupling loss between the lensed fibre and the Si$_3$N$_4$ chip amounts to approximately 3~dB per facet. In the data transmission experiments we pump a resonance near 1549.4~nm. The tunable fibre Bragg grating (FBG~1) at the output of the device suppresses the remaining pump signal by approximately 20~dB. The ring resonator consists of nearly stoichiometric Si$_3$N$_4$ grown in multiple layers with intermediate annealing steps \citep{levy2010}. The strip waveguides are patterned with electron beam lithography and transferred to the substrate by reactive ion etching with SF$_6$/CH$_4$ chemistry. The waveguides are then embedded into a SiO$_2$ cladding using low-pressure chemical vapour deposition (LPCVD). The waveguides are 2~\micro m wide and 750~nm high, and the sidewalls are inclined by 12$^\circ$ with respect to the vertical direction (Fig.~\ref{Fig2}, Inset 1).

The high-temperature growth technique used to fabricate the 750~nm thick layers of stoichiometric Si$_3$N$_4$ requires annealing at 1200$^\circ$C. This makes it difficult to fabricate SiN resonators in the framework of standard CMOS processes. One option to overcome these limitations is to use dedicated fabrication processes and multi-chip integration as illustrated in Fig.~\ref{Fig1}. Alternatively, it is possible is to deposit Si$_3$N$_4$ at 400$^\circ$C and to use UV thermal processing (UVTP) at lower temperatures to reduce the defect density. Both techniques are subject to ongoing research.

In the first data transmission experiment, the resonator exhibits a free spectral range (FSR) of 17~GHz, and a loaded Q-factor of $8\times10^5$. Kerr combs are generated using an on-chip pump power of approximately 33~dBm. For the second experiment, we fabricated a resonator with a FSR of 25~GHz, which exhibits an increased Q-factor of $2\times10^{6}$. The comb is generated with approximately 29~dBm of on-chip pump power, and the measured line spacing deviates by less than 6~MHz from the designed 25~GHz. We expect that microresonators with further improved Q-factors will enable generation of broadband frequency combs with hundreds of lines that cover optical bandwidths of hundreds of nanometers - a multiple of what can be achieved with state-of-the-art distributed-feedback WDM laser arrays in InGaAsP technology. Note that in the envisaged system illustrated in Fig.~\ref{Fig1}, the use of FBG for pump light suppression will become superfluous: If the frequency comb is extracted by a second waveguide coupled to the ring resonator, direct through-coupling of strong cw pump light is not possible, and FBG notch filters are not needed.

\subsection*{Generation of low phase-noise Kerr combs.}
To obtain low phase-noise Kerr combs, the pump parameters are adjusted in two steps using the setup depicted in Fig.~\ref{Fig2}: First, the pump wavelength is periodically scanned across the resonance at a frequency of approximately 100~Hz while staying within the stop band of FBG~2 and continuously measuring the power conversion to the spectral region outside the stop band. During these scans the polarization of the pump signal is slowly varied to maximize the conversion. Maintaining this polarization, the detuning of the pump signal with respect to the resonance wavelength is then carefully adjusted until the initially broad RF spectrum (Fig.~\ref{Fig2}, Inset 3) exhibits a single narrow peak (Fig.~\ref{Fig2}, Inset 4). Note that the frequency axes of Insets 3 and 4 have different scales. The power spectrum of Inset 3 was recorded with a resolution bandwidth (RBW) of 10~kHz whereas Inset 4 was recorded with a RBW of 30~kHz. For an on-chip pump power of approximately 33~dBm the essential part of the optical comb spectrum is depicted in Inset 5 of Fig.~\ref{Fig2}. From this partial spectrum we selected the lines for our data transmission experiments. Spectra of the comb used for the second experiment can be found in the SI.

The on-chip pump power needed for Kerr comb generation in the first and in the second experiment, still amounts to 33~dBm and 29~dBm, respectively. However, there is considerable room for future improvements - Kerr combs have been demonstrated with a threshold power as low as 50~\micro W in silica toroids \citep{haye2007}. In general, the threshold for Kerr comb generation scales inversely quadratic with the Q-factor of the resonator \citep{kippenberg2004a}. A 10-fold Q-factor improvement would lead to a reduction of the pump power by a factor of 100 and the 2~Watt pump laser could be replaced by 20~mW pump laser diode.

\subsection*{Feedback stabilization of a Kerr comb. }
To maintain low-phase noise comb states during an extended data transmission experiment, it is important to keep the pump conditions as constant as possible. In the first experiment, we found that the on-chip pump power is a crucial parameter and must be kept constant to approximately $\pm$5~\% to maintain thermal locking of the cavity resonance to the pump wavelength \citep{carmon2004}. The second experiment relies on stable comb generation for extended studies of data transmission performance. This is achieved by an independent control loop based on commercially available hardware (Melles Griot NanoTrak) that keeps the lensed fibres in the optimum coupling position. In addition, we implemented a second control loop using a commercially available PID controller (TEM Messtechnik LaseLock), which takes the power in the comb lines as feedback signal and controls the pump laser detuning such that thermal drifts of the resonator are followed by slight adaptation of the pump wavelength, see SI for a more detailed discussion. The combination of these two control loops enables stable Kerr comb operation over several hours without human interaction.

\begin{figure*}
\includegraphics[width=1\textwidth]{Fig5_comb_stable_setup.png}

\caption{\textbf{Generation and stabilization of a Kerr frequency comb in the second transmission experiment. a,} The experimental setup is similar to the one used in the first experiment, see Fig.~\ref{Fig2}. Due to an improved Q-factor, the pump power could be reduced which allows filtering of the ASE noise originating from the pump EDFA using a 2~nm band pass filter (BPF). The resonator (inset 1) exhibits a FSR of 25~GHz and a loaded Q-factor of $2\times10^{6}$. Using an on-chip power of 29~dBm, we pump a resonance near 1549.4~nm. The pump parameters are manually adjusted using the scheme described in the Methods Section. The insets on the right-hand side show the RF (top) and optical (mid and bottom) spectra of the resulting comb. For a stable comb output, we control the wavelength of the pump laser. As a feedback signal, we use the comb power $P_{comb}$ measured behind FBG~1. \textbf{b,} $P_{comb}$ (left axis, orange) and the total power $P_{tot}$ measured at the output of the chip (right axis, black) as a function of the detuning $\delta\lambda$ from the cold cavity resonance. The circle indicates the operation point of the control loop, which corresponds to the manually adjusted low phase-noise comb state. The control loop is activated after the pump parameters have been optimized. \textbf{c,} Feedback and wavelength control signal for a time frame of three hours. The pump wavelength follows the thermal drifts of the resonance, which leads to perfectly stable comb output power.}
\label{Fig5}
\end{figure*}

\subsection*{Signal impairment analysis. }
In the first experiment, the optical carrier-to-noise-density ratio (OCN$_0$R) is limited by the ASE noise originating from the pump amplifier. To determine the OCN$_0$R, we need to estimate the noise power density right at the frequency of the respective comb line. This is done by averaging the spectral power densities obtained in the middle between two comb lines. The spectral power densities were measured with an optical spectrum analyser (Ando AQ 6317B) in a 0.01~nm bandwidth and renormalized to a bandwidth of 1~Hz.

\begin{figure*}
\includegraphics[width=1\textwidth]{Fig6_data_setup.png}

\caption{\textbf{Data transmission setup.} A tunable delay interferometer (DI) is used to separate the incoming frequency comb into carriers that belong to odd and even channels. The two sets of channels are then separately modulated at a symbol rate of 14~GBd using QPSK or 16QAM signals and Nyquist sinc-pulses. The two data streams are merged and fed into a polarization multiplexer (PolMUX), comprising a half-wave plate (HWP), a delay line and a polarization beam splitter (PBS). The PolMUX splits the optical signal in two parts, delays one of them to form two uncorrelated data streams, and recombines them on two orthogonal polarization states of the standard single-mode transmission fibre (SSMF). The receiver comprises an erbium-doped fibre amplifier (EDFA), an optical band-pass filter (BPF), and an optical modulation analyzer (OMA) with a tunable laser serving as a local oscillator (LO). Digital signal processing in the baseband is used to separate the WDM channels and to demultiplex the polarizations. Insets: \textbf{1,} Spectra of the unmodulated carriers after separation by the DI. Even channels are represented by the magenta solid line, odd channels by the red dotted line. The extinction ratio is better than 20~dB for all channels; \textbf{2,} Optical spectrum at the input of the OMA, after the 2~nm band-pass filter. The pronounced noise background predominantly originates from the ASE of the pump EDFA that is used for frequency comb generation. }
\label{Fig6}
\end{figure*}

To improve the signal quality, it is possible to filter out ASE by using a band-pass filter before the DUT as demonstrated in the second experiment. When performing the first experiment, however, we did not have any filters that could safely handle the 37~dBm of pump power right after the EDFA. We showed that by further optimizing the fabrication process, we can increase the microresonator's Q-factor and hence significantly decrease the required threshold power \citep{kippenberg2004a}, such that filtering of the pump signal was possible. In addition the comb may be extracted by a second waveguide which is coupled to the microresonator, see Fig.~\ref{Fig1}. This avoids direct transmission of broadband ASE noise transmitted through the resonator device. Using resonators with higher Q-factor, it might even be possible to use a high-power pump laser diode without requiring amplification at all.

\section*{Supplementary Information}

\subsection*{Feedback-stabilization of a Kerr frequency comb}

To maintain low phase-noise comb states during the second experiment, we have implemented a control loop that takes the power $P_{comb}$ measured at the output of FBG~2 as a feedback signal and adjusts the wavelength of the pump laser to ensure a constant detuning. Fig.~\ref{Fig5}a shows the comb generation setup along with the control loop. The principle of the feedback stabilization is illustrated in Fig.~\ref{Fig5}b, which shows $P_{comb}$ (orange trace, left axis) and the total chip output power $P_{tot}$ (black trace, right axis) as a function of the detuning $\delta\lambda$ between the pump wavelength and the resonance wavelength of the cold cavity. As the wavelength of the pump is scanned, it drags along the resonance through thermal locking. This leads to a continuous decrease of $P_{tot}$ until locking is lost for large detuning. At the same time, $P_{comb}$ exhibits a pronounced increase once the power coupled to the cavity reaches the threshold for Kerr comb generation. Our control loop is based on a commercially available PID controller (TEM Messtechnik LaseLock) and operates at the rising edge of $P_{comb}$. The circle in Fig.~\ref{Fig5}b indicates the operation point that corresponds to the low phase-noise comb state for which the pump parameters have been manually optimized before starting the control. Moreover, for stable comb generation, it is crucial that also the fibre-chip coupling efficiency is actively stabilized. To this end, we use an independent control loop based on commercially available hardware (Melles Griot NanoTrak) to keep the lensed fibres in the optimum coupling position. We confirm the functionality of the feedback stabilization by recording the feedback signal and the comb power for more than 3h, Fig.~\ref{Fig5}c. The pump wavelength follows the thermal drifts of the resonance, and residual comb power fluctuations are found to be well below 1~\%. Comb spectra measured at the beginning and at the end of the extended data transmission experiment are indistinguishable within the accuracy of our spectrometer (ANDO AQ 6317B).

\subsection*{Experimental setup for WDM data transmission}

To emulate a WDM communication system, we transmit data on all channels simultaneously, using one pseudo-random bit sequence (PRBS) on the even channels and another independent PRBS on the odd channels. Neighbouring channels hence carry uncorrelated data streams, and inter-channel crosstalk translates directly into a degradation of signal quality. For the first data transmission experiment, the corresponding setup is depicted in Fig.~\ref{Fig6}. Carriers belonging to odd and even channels are first separated by a tunable delay interferometer (DI) \citep{li2011}. The superposition of both spectra is displayed in Inset 1 of Fig.~\ref{Fig6}. Two home-built multi-format transmitters \citep{schmogrow2010} are then used to encode QPSK or 16QAM signals with a symbol rate of 14~GBd on the sets of even and odd carriers using independent PRBS with a length of $2^{15} - 1$. Polarization-division multiplexing (PDM) is emulated by splitting the optical signal, and recombining the original and a sufficiently delayed copy to form two decorrelated data streams on orthogonal polarizations. The data stream is transmitted to the receiver, where the signal is amplified, filtered and coherently detected using an optical modulation analyser (OMA, Agilent N 4391 A) with a standard tunable laser (Agilent 81680A) acting as a local oscillator (LO). An optical bandpass filter with a 2~nm passband is used to avoid saturation of the receiver photodiodes. Individual WDM channels are selected by appropriate choice of the LO wavelength and by digital brick-wall filtering in the baseband. Inset 2 of Fig.~\ref{Fig6} shows the optical spectrum at the input of the OMA. The effect of the 2~nm band-pass filter is clearly visible; the noise in the pass-band predominantly originates from the ASE of the pump EDFA that is used for frequency comb generation.

For the second data transmission experiment, the setup differs only slightly from the one depicted in Fig.~\ref{Fig6}: Instead of the delay interferometer, we use a programmable filter (Finisar WaveShaper) to separate the comb lines, which additionally allows flattening the spectral envelope of the comb. Moreover, we only use QPSK as a modulation format, and increase the symbol rate to 18~GBd. In addition to back-to-back testing, we transmit the signal over up to four spans of 75~km standard single mode fibre (SSMF) with an EDFA set to an output power of 10~dBm before each span.

In both transmission experiments, digital post-processing comprises demultiplexing of the polarization channels, compensation of the frequency offset between the LO and the optical carrier, clock recovery, equalization, and dispersion compensation where applicable. For performance evaluation we use the error-vector magnitude (EVM) metric, which describes the effective distance of a received complex symbol from its ideal position in the constellation diagram. Provided that the signal is impaired by additive white Gaussian noise only, the EVM is directly related \citep{schmogrow2012a} to the bit-error ratio (BER). For 16QAM, we estimate a BER of $3\times10^{-4}$ from the measured EVM of 10~\%, which is in fair agreement with the measured BER of $7.5\times10^{-4}$. This confirms the validity of the EVM-based estimation of the BER in our experiment. For the other QPSK channels, the BER of $3\times10^{-7}$, $7\times10^{-8}$, $1\times10^{-8}$, $1\times10^{-11}$, and $5\times10^{-20}$ are estimated accordingly from the measured EVM values of 20~\%, 19~\%, 18~\%, 15~\%, and 11~\%. Channels 4 and 5 hence feature BER, well below the threshold of $10^{-9}$, which is commonly considered error-free in telecommunications. This clearly demonstrates that error-free data transmission with Kerr combs is possible and that the achievable BER is rather limited by the components of the transmission system such as modulators, amplifiers and filters than by the coherence of the light source.

Apart from the ASE of the pump EDFA as discussed in the Methods Section, we investigated coherent crosstalk as a potential source of signal degradation: In the first experiment, the tunable DI used to separate the carriers has a finite extinction ratio (ER), see Inset 1 in Fig.~\ref{Fig6}. As a consequence, the data signals of the even channels are superimposed by residual carriers modulated with odd-channel data and vice versa, which leads to further signal degradation. However, in our experiment this effect was not relevant: With an ER better than ($22.2\pm1.5$)~dB for all channels, no correlation of channel ER and EVM can be observed. In the second experiment using the programmable filter we achieve an ER of ($24.6\pm4.0$)~dB. Coherent crosstalk can therefore safely be excluded as a source of signal degradation.

\newpage

\renewcommand{\emph}{\textit}
\bibliographystyle{naturemag}


\section{Introduction}

A mapping of the domain $\{0,1,\dots,m-1\}\times\{0,1,\dots,n-1\}$ into $\{0,1\}$,
is called a {\em threshold function} iff there exists a line separating the sets of its ones and zeros
(points at which the function takes values $1$ and $0$, respectively).

A \emph{teaching set} of a threshold function $g$ is a subset of its domain
such that the values of $g$ at the points from this set uniquely define the function.
A teaching set of $g$ is called {\em minimal} (or {\em irreducible}) iff no its proper subset is teaching for $g$.
It is known (e.g., see \cite{ABS1995,ShevchenkoZolotykh1998,ZolotykhShevchenko1999})
that the minimal teaching set $T(g)$ for any threshold function $g$ is unique
(this also holds for threshold functions in higher dimensions).
In \cite{ShevchenkoZolotykh1998,Zolotykh2001} it is proved that $T(g)$ consists of $3$ or $4$ points if $m\ge 2$, $n\ge 2$.
Here we derive exact formulae for the number of threshold functions corresponding to these values.
In the case when $T(g)$ consists of $3$ points, we further compute the number of threshold functions $g$ with the specified number (one or two) of zeros
in $T(g)$, answering the question posed in \cite{Alekseyev2010}.
We also prove that the average cardinality of the minimal teaching set is asymptotically $\nicefrac{7}{2}$ as $m,n\to\infty$.
Finally, we discuss some corollaries of this result concerning special arrangements of lines in the plane.

We remark that the cardinality of the minimal teaching set of threshold functions defined on {\em many\,}-dimensional
grid is studied in a number of publications (e.g., see the bibliography in \cite{Zolotykh2008}).
In particular, the bounds of the average cardinality of the minimal teaching set of threshold functions are given in \cite{ABS1995,VirovlyanskayaZolotykh2003}.

\section{Preliminary definitions and results}

Let $m\ge 2$, $n\ge 2$, $E_m=\{0,1,\dots,m-1\}$, $g:~E_m\times E_n \to \{0,1\}$.
We denote by $M_0(g)$, $M_1(g)$ the set of zeros and the set of ones of $g$, respectively, that is
$$
M_{\nu}(g) = \{x=(x_1, x_2)\in E_m\times E_n:~f(x)=\nu\}
\quad
(\nu \in \{0,1\}).
$$
The function $g$ is called {\em threshold} iff there exist real numbers $a_0$, $a_1$, $a_2$ such that
\begin{equation}
M_0(g) = \{(x_1,x_2)\in E_m\times E_n\ :\ a_1 x_1 + a_2 x_2 \le a_0 \}.
\label{eq:M0}
\end{equation}
Without loss of generality we can assume that the numbers $a_0$, $a_1$, $a_2$ are integer and $a_1$, $a_2$ are not zero simultaneously.
We call the line $a_1 x_1 + a_2 x_2 = a_0$ a {\em separation line} for the threshold function $g$.
Note that for any line $a_1 x_1 + a_2 x_2 = a_0$, there are two associated threshold functions:
a function $g$ defined by \eqref{eq:M0} holds and a function $h$ with $M_0(h) = \{(x_1,x_2)\in E_m\times E_n\ :\ a_1 x_1 + a_2 x_2 > a_0 \}$, which also satisfy
$g(x)+h(x)=1$ for any $x\in E_m\times E_n$.

Let ${\cal T}(m,n)$ be the set of all threshold functions defined on $E_m\times E_n$ and $t(m,n)=|{\cal T}(m,n)|$.

Denote
$$
f_q(m,n) = \sum_{\substack{-m<i<m\\ -n<j<n\\ \gcd(i,j)=q}} (m-|i|)(n-|j|).
$$

Two distinct points $p$, $p'$ in $E_m \times E_n$ are called {\em adjacent}
if and only if the line segment $[p,p']$ contains no other point from $E_m \times E_n$.

\begin{lemma}[\cite{AcketaZunic1991,KLB1990}] \label{lemma_adj}
The number of ordered pairs $(p, p')$ of adjacent points in $E_m\times E_n$ equals $f_1(m,n)$.
\end{lemma}

\begin{lemma}[\cite{HaukkanenMerikoski2013}] \label{lemma_fqmn}
If $m\le n$ then
$$
f_q(m,n) = \frac{6}{\pi^2 q^2}(mn)^2 + O(mn^2).
$$
\end{lemma}

Denote by $l(m,n)$ the number of lines passing through at least two points in $E_m\times E_n$.
\begin{lemma}[\cite{Mustonen2009,HaukkanenMerikoski2012}]
\begin{equation}
l(m,n) = \frac{1}{2}\left(f_1(m,n) - f_2(m,n) \right).
\label{eq:lmnf1f2}
\end{equation}
\end{lemma}

\begin{theorem}[\cite{KLB1990}] \label{th_tmn}
\begin{equation}
t(m,n) = f_1(m,n) + 2.
\label{eq:tmnfmn}
\end{equation}
\end{theorem}

\begin{corollary}
\begin{equation}
t(m,n) = 2 + \sum_{\substack{-m<i<m\\ -n<j<n\\ \gcd(i,j)=1}} (m-|i|)(n-|j|) = \frac{6}{\pi^2}(mn)^2 + O(mn^2),
\label{eq:tmnass}
\end{equation}
where asymptotics holds for $m\le n$.
\end{corollary}

We remark that the asymptotic behavior of $t(m,n)$ was studied by many authors (sometimes using different terminology), for example,
\cite{KLB1990,AcketaZunic1991,Shevchenko1995,Alekseyev2010,Zunic2011,HaukkanenMerikoski2013}.

\begin{figure}
\begin{center}

\begin{tabular}{lr}

\psset{xunit=.7cm,yunit=.7cm}
\begin{pspicture}(-1,-2)(10,10)

  \rput[t](4.5,-1.3){$7x_1 + 5x_2 \le 55$}

  \pspolygon[fillstyle=solid,fillcolor=lightgray,linecolor=lightgray](8.21429,-0.5)(0.7143,10)(-0.0994,9.4188)(7.4006,-1.0812)
  \psline(8.21429,-0.5)(0.7143,10)

  \psline[arrows=->](10,0)
  \psline[arrows=->](0,10)
  \rput[lb](10.2,0.15){$x_1$}
  \rput[lb](0.15,10.15){$x_2$}
  \rput[t](0,-0.3){$0$}
  \rput[t](9,-0.3){$9$}
  \rput[r](-0.3,9){$9$}
  \psline(0,9)(9,9)(9,0)
  \rput(2.5,2.5){$M_0(g)$}
  \rput(6.5,6.5){$M_1(g)$}

  \psdots[dotstyle=o,dotscale=3](5,4)
  \psdots[dotstyle=o,dotscale=3](8,0)(3,7)

  \psdots[dotstyle=o](0,0)\psdots[dotstyle=o](1,0)\psdots[dotstyle=o](2,0)\psdots[dotstyle=o](3,0)\psdots[dotstyle=o](4,0)\psdots[dotstyle=o](5,0)
  \psdots[dotstyle=o](0,1)\psdots[dotstyle=o](1,1)\psdots[dotstyle=o](2,1)\psdots[dotstyle=o](3,1)\psdots[dotstyle=o](4,1)\psdots[dotstyle=o](5,1)
  \psdots[dotstyle=o](0,2)\psdots[dotstyle=o](1,2)\psdots[dotstyle=o](2,2)\psdots[dotstyle=o](3,2)\psdots[dotstyle=o](4,2)\psdots[dotstyle=o](5,2)
  \psdots[dotstyle=o](0,3)\psdots[dotstyle=o](1,3)\psdots[dotstyle=o](2,3)\psdots[dotstyle=o](3,3)\psdots[dotstyle=o](4,3)\psdots[dotstyle=o](5,3)
  \psdots[dotstyle=o](0,4)\psdots[dotstyle=o](1,4)\psdots[dotstyle=o](2,4)\psdots[dotstyle=o](3,4)\psdots[dotstyle=o](4,4)\psdots[dotstyle=o](5,4)
  \psdots[dotstyle=o](0,5)\psdots[dotstyle=o](1,5)\psdots[dotstyle=o](2,5)\psdots[dotstyle=o](3,5)\psdots[dotstyle=o](4,5)\psdots[          ](5,5)
  \psdots[dotstyle=o](0,6)\psdots[dotstyle=o](1,6)\psdots[dotstyle=o](2,6)\psdots[dotstyle=o](3,6)\psdots[          ](4,6)\psdots[          ](5,6)
  \psdots[dotstyle=o](0,7)\psdots[dotstyle=o](1,7)\psdots[dotstyle=o](2,7)\psdots[          ](3,7)\psdots[          ](4,7)\psdots[          ](5,7)
  \psdots[dotstyle=o](0,8)\psdots[dotstyle=o](1,8)\psdots[dotstyle=o](2,8)\psdots[          ](3,8)\psdots[          ](4,8)\psdots[          ](5,8)
  \psdots[dotstyle=o](0,9)\psdots[dotstyle=o](1,9)\psdots[          ](2,9)\psdots[          ](3,9)\psdots[          ](4,9)\psdots[          ](5,9)

  \psdots[dotstyle=o](6,0)\psdots[dotstyle=o](7,0)\psdots[          ](8,0)\psdots[          ](9,0)
  \psdots[dotstyle=o](6,1)\psdots[dotstyle=o](7,1)\psdots[          ](8,1)\psdots[          ](9,1)
  \psdots[dotstyle=o](6,2)\psdots[          ](7,2)\psdots[          ](8,2)\psdots[          ](9,2)
  \psdots[          ](6,3)\psdots[          ](7,3)\psdots[          ](8,3)\psdots[          ](9,3)
  \psdots[          ](6,4)\psdots[          ](7,4)\psdots[          ](8,4)\psdots[          ](9,4)
  \psdots[          ](6,5)\psdots[          ](7,5)\psdots[          ](8,5)\psdots[          ](9,5)
  \psdots[          ](6,6)\psdots[          ](7,6)\psdots[          ](8,6)\psdots[          ](9,6)
  \psdots[          ](6,7)\psdots[          ](7,7)\psdots[          ](8,7)\psdots[          ](9,7)
  \psdots[          ](6,8)\psdots[          ](7,8)\psdots[          ](8,8)\psdots[          ](9,8)
  \psdots[          ](6,9)\psdots[          ](7,9)\psdots[          ](8,9)\psdots[          ](9,9)

\end{pspicture}

&

\psset{xunit=.7cm,yunit=.7cm}
\begin{pspicture}(-1,-2)(10,10)

  \rput[t](4.5,-1.3){$3x_1 + 2x_2 \le 22$}

  \pspolygon[fillstyle=solid,fillcolor=lightgray,linecolor=lightgray](7.66667,-0.5)(0.666667,10)(-0.1654,9.4453)(6.8346,-1.0547)
  \psline(7.66667,-0.5)(0.666667,10)

  \psline[arrows=->](10,0)
  \psline[arrows=->](0,10)
  \rput[lb](10.2,0.15){$x_1$}
  \rput[lb](0.15,10.15){$x_2$}
  \rput[t](0,-0.3){$0$}
  \rput[t](9,-0.3){$9$}
  \rput[r](-0.3,9){$9$}
  \psline(0,9)(9,9)(9,0)
  \rput(2.5,2.5){$M_0(h)$}
  \rput(6.5,6.5){$M_1(h)$}

  \psdots[dotstyle=o,dotscale=3](6,2)(2,8)
  \psdots[dotstyle=o,dotscale=3](7,1)(3,7)

  \psdots[dotstyle=o](0,0)\psdots[dotstyle=o](1,0)\psdots[dotstyle=o](2,0)\psdots[dotstyle=o](3,0)\psdots[dotstyle=o](4,0)\psdots[dotstyle=o](5,0)
  \psdots[dotstyle=o](0,1)\psdots[dotstyle=o](1,1)\psdots[dotstyle=o](2,1)\psdots[dotstyle=o](3,1)\psdots[dotstyle=o](4,1)\psdots[dotstyle=o](5,1)
  \psdots[dotstyle=o](0,2)\psdots[dotstyle=o](1,2)\psdots[dotstyle=o](2,2)\psdots[dotstyle=o](3,2)\psdots[dotstyle=o](4,2)\psdots[dotstyle=o](5,2)
  \psdots[dotstyle=o](0,3)\psdots[dotstyle=o](1,3)\psdots[dotstyle=o](2,3)\psdots[dotstyle=o](3,3)\psdots[dotstyle=o](4,3)\psdots[dotstyle=o](5,3)
  \psdots[dotstyle=o](0,4)\psdots[dotstyle=o](1,4)\psdots[dotstyle=o](2,4)\psdots[dotstyle=o](3,4)\psdots[dotstyle=o](4,4)\psdots[          ](5,4)
  \psdots[dotstyle=o](0,5)\psdots[dotstyle=o](1,5)\psdots[dotstyle=o](2,5)\psdots[dotstyle=o](3,5)\psdots[dotstyle=o](4,5)\psdots[          ](5,5)
  \psdots[dotstyle=o](0,6)\psdots[dotstyle=o](1,6)\psdots[dotstyle=o](2,6)\psdots[dotstyle=o](3,6)\psdots[          ](4,6)\psdots[          ](5,6)
  \psdots[dotstyle=o](0,7)\psdots[dotstyle=o](1,7)\psdots[dotstyle=o](2,7)\psdots[          ](3,7)\psdots[          ](4,7)\psdots[          ](5,7)
  \psdots[dotstyle=o](0,8)\psdots[dotstyle=o](1,8)\psdots[dotstyle=o](2,8)\psdots[          ](3,8)\psdots[          ](4,8)\psdots[          ](5,8)
  \psdots[dotstyle=o](0,9)\psdots[dotstyle=o](1,9)\psdots[          ](2,9)\psdots[          ](3,9)\psdots[          ](4,9)\psdots[          ](5,9)

  \psdots[dotstyle=o](6,0)\psdots[dotstyle=o](7,0)\psdots[          ](8,0)\psdots[          ](9,0)
  \psdots[dotstyle=o](6,1)\psdots[          ](7,1)\psdots[          ](8,1)\psdots[          ](9,1)
  \psdots[dotstyle=o](6,2)\psdots[          ](7,2)\psdots[          ](8,2)\psdots[          ](9,2)
  \psdots[          ](6,3)\psdots[          ](7,3)\psdots[          ](8,3)\psdots[          ](9,3)
  \psdots[          ](6,4)\psdots[          ](7,4)\psdots[          ](8,4)\psdots[          ](9,4)
  \psdots[          ](6,5)\psdots[          ](7,5)\psdots[          ](8,5)\psdots[          ](9,5)
  \psdots[          ](6,6)\psdots[          ](7,6)\psdots[          ](8,6)\psdots[          ](9,6)
  \psdots[          ](6,7)\psdots[          ](7,7)\psdots[          ](8,7)\psdots[          ](9,7)
  \psdots[          ](6,8)\psdots[          ](7,8)\psdots[          ](8,8)\psdots[          ](9,8)
  \psdots[          ](6,9)\psdots[          ](7,9)\psdots[          ](8,9)\psdots[          ](9,9)

\end{pspicture}

\end{tabular}

\end{center}
\caption{Threshold functions $g,h$ on $E_{10}\times E_{10}$ with $|T(g)|=3$ (left panel) and $|T(h)|=4$ (right panel) and their separation lines.
The empty dots represent zeros of the function, while the circled dots form its minimal teaching set.}\label{fig_exTf}
\end{figure}

\section{Cardinality of minimal teaching sets}

A set $T\subseteq E_m\times E_n$ is called {\em teaching} for $g\in{\cal T}(m,n)$
iff for any other function $h\in{\cal T}(m,n)$ there exists $x\in T$ such that $g(x)\ne h(x)$.
A teaching set of $g$ is called {\em minimal} or {\em irreducible} iff no its proper subset is teaching for $g$.
A point $x \in E_m\times E_n$ is called {\em essential} for $g\in{\cal T}(m,n)$ iff there exists $h\in{\cal T}(m,n)$
such that $g(x)\ne h(x)$ and $g(y)=h(y)$ for all $y\ne x$.

\begin{lemma}[\cite{ABS1995,ShevchenkoZolotykh1998,ZolotykhShevchenko1999}] \label{lemma_Tunique}
For any function $g\in{\cal T}(m,n)$, the minimal teaching set of $g$ is unique and consists of all essential points of $g$.
\end{lemma}
We remark that Lemma~\ref{lemma_Tunique} also holds for threshold functions defined on many-dimensional grid.

Denote by $T(g)$ the minimal teaching set of $g$.
In~\cite{ShevchenkoZolotykh1998,Zolotykh2001} it is shown that $|T(g)|\in\{3,4\}$ for any function $g\in{\cal T}(m,n)$
(see examples in Fig.~\ref{fig_exTf}).

We define the {\em average cardinality} of the minimal teaching sets as
\begin{equation}
\overline{\sigma}(m,n) = \frac{1}{t(m,n)} \sum_{g\in{\cal T}(m,n)} |T(g)|.
\label{eq:osdef}
\end{equation}

\begin{theorem} \label{osmn}
\begin{equation}
\overline{\sigma}(m,n) = \frac{4\cdot f_1(m,n)-2\cdot f_2(m,n)}{f_1(m,n)+2}.
\label{eq:osfff1}
\end{equation}
\end{theorem}

\begin{proof}
Denote by $h(m,n,i,j)$ the number of threshold functions defined on the domain $E_m\times E_n$ such
that the point $(i,j)$ is essential. By Lemma \ref{lemma_Tunique},
\begin{equation}
\overline{\sigma}(m,n) = \frac{1}{t(m,n)} \sum_{g\in {\cal T}(m,n)} |T(g)| = \frac{1}{t(m,n)} \sum_{i=0}^{m-1}\sum_{j=0}^{n-1} h(m,n,i,j).
\label{eq:osmnh}
\end{equation}

\begin{figure}
\begin{center}

\psset{xunit=1.7cm,yunit=1.7cm}
\begin{pspicture}(-0.75,-1)(4,4)

  \psline[linewidth=1pt](1.35,-0.4)(0.4,3.4)

  \psline[arrows=->](3.5,0)
  \psline[arrows=->](0,3.75)
  \rput(3.65,0.15){$x_1$}
  \rput[r](0,3.8){$x_2$~}
  \psline(-0.2,1)(3.2,1)
  \psline(0,3)(3,3)
  \psline(1,-0.2)(1,3.2)
  \psline(3,0)(3,3)
  \psline(-0.2,-0.2)(3.2,3.2)
  \psline(-0.2,2.2)(2.2,-0.2)
  \psline(-0.1,3.2)(1.6,-0.2)
  \psline(2.1,3.2)(0.4,-0.2)
  \psline(3.2,2.1)(-0.2,0.4)
  \psline(3.2,-0.1)(-0.2,1.6)

  \psdots[dotstyle=o](0,3) \psdots[          ](1,3) \psdots[ ](2,3) \psdots[ ](3,3)
  \psdots[dotstyle=o](0,2) \psdots[          ](1,2) \psdots[ ](2,2) \psdots[ ](3,2)
  \psdots[dotstyle=o](0,1) \psdots[dotstyle=o](1,1) \psdots[ ](2,1) \psdots[ ](3,1)
  \psdots[dotstyle=o](0,0) \psdots[dotstyle=o](1,0) \psdots[ ](2,0) \psdots[ ](3,0)

  \rput(0,-0.2){$0$}
  \rput[r](1,-0.2){$1~$}
  \rput(2,-0.2){$2$}
  \rput(3,-0.2){$3$}
  \rput(-0.15,0.85){$1$}
  \rput(-0.15,1.95){$2$}
  \rput(-0.15,3){$3$}

\rput(0.6,3.4){$\ell'$}

\end{pspicture}

\caption{The lines forming $L(4,4,1,1)$ with $l(4,4,1,1) = 8$ and a line $\ell'\notin L(4,4,1,1)$
defining two threshold functions.
}
\label{Fig2}

\end{center}
\end{figure}

Let us consider all lines containing the point $(i,j)$ and at least one other point from $E_m\times E_n$.
Denote by $L(m,n,i,j)$ the set of all such lines (see Fig.~\ref{Fig2}) and
let $l(m,n,i,j) = |L(m,n,i,j)|$.
The lines from $L(m,n,i,j)$ partition the plane into $2\cdot l(m,n,i,j)$ sectors.

It is easy to see that any line $\ell'\notin L(m,n,i,j)$ containing the point $(i,j)$ is associated with two threshold functions,
for which the point $(i,j)$ is essential and a zero (Fig.~\ref{Fig2}).
It is clear that these functions are uniquely determined by the two lines from $L(m,n,i,j)$ adjacent to $\ell'$.
Moreover, there is no other function in ${\cal T}(m,n)$, for which the point $(i,j)$ is essential and a zero.

Thus, we have $2\cdot l(m,n,i,j)$ threshold functions for which the point $(i,j)$ is essential and a zero.
We have the same number of functions for which the point $(i,j)$ is essential and not a zero (i.e., the value at $(i,j)$ is $1$).
Hence $h(m,n,i,j) = 4\cdot l(m,n,i,j)$.
Now from \eqref{eq:osmnh} we get
\begin{equation}
\label{eq:osmnh2}
\overline{\sigma}(m,n) = \frac{4}{t(m,n)} \sum_{i=0}^{m-1}\sum_{j=0}^{n-1} l(m,n,i,j).
\end{equation}

Let $L(m,n)$ be the set of all lines passing through at least two points from $E_m\times E_n$ and $l(m,n)=|L(m,n)|$.
For a line $\ell \in L(m,n)$, we denote by $z(m,n,\ell)$ the number of points in $E_m\times E_n$ belonging to $\ell$.
Now from \eqref{eq:osmnh2} we get
$$
\overline{\sigma}(m,n)
= \frac{4}{t(m,n)} \sum_{\ell\in L(m,n)} z(m,n,\ell).
$$
We remark that if $\ell$ contains exactly $k$ points from $E_m\times E_n$, then they form $k-1$ adjacent pairs of points.
Then by Lemma~\ref{lemma_adj},
$$
\overline{\sigma}(m,n) = 4\cdot \frac{l(m,n)+\frac{1}{2}f_1(m,n)}{t(m,n)}.
$$
Substituting here the expressions \eqref{eq:lmnf1f2} and \eqref{eq:tmnfmn}, we obtain \eqref{eq:osfff1}.
\end{proof}

Theorem~\ref{osmn} and Lemma~\ref{lemma_fqmn} imply the following asymptotics for $\overline{\sigma}(m,n)$.

\begin{corollary}\label{cor72} For $m\le n$,
$$
\overline{\sigma}(m,n) = \frac{7}{2} + O\left(\frac{1}{m}\right).
$$
\end{corollary}

Denote by $t_{\kappa}(m,n)$ the number of functions $g\in{\cal T}(m,n)$ such that $|T(g)|=\kappa$ ($\kappa\in\{3,4\}$).
Corollary~\ref{cor72} implies that each of the quantities $t_3(m,n)$ and $t_4(m,n)$ is asymptotically $\frac{1}{2}t(m,n)$.
Below we give exact formulae for $t_3(m,n)$ and $t_4(m,n)$.

\begin{theorem}\label{th_t3t4}
\begin{eqnarray*}
t_3(m,n) &=& 2\cdot f_2(m,n) + 8,\\
t_4(m,n) &=& f_1(m,n) - 2\cdot f_2(m,n) - 6.
\end{eqnarray*}
\end{theorem}
\begin{proof}
From the conditions
$$
t_3(m,n) + t_4(m,n) = t(m,n), \qquad \overline{\sigma}(m,n) = \frac{3\cdot t_3(m,n) + 4\cdot t_4(m,n)}{t(m,n)},
$$
we obtain
$$
t_3(m,n) = \left(4 - \overline{\sigma}(m,n)\right)\cdot t(m,n), \qquad t_4(m,n) = \left(\overline{\sigma}(m,n) - 3\right)\cdot t(m,n).
$$
Substitution of the expressions \eqref{eq:tmnfmn} and \eqref{eq:osfff1} here completes the proof.
\end{proof}

\section{Minimal teaching sets of size $3$}

It is known that a minimum teaching set of a non-constant threshold function $g$ with $|T(g)|=4$ always contains two zeros~\cite{Zolotykh2001}.
The threshold functions $g$ with $|T(g)|=3$ can be classified depending on whether their minimal teaching sets contain one or two zeros.
The question of counting threshold functions in these classes was posed and partially answered in~\cite{Alekseyev2010}.
Below we give a complete answer to this question.

Let $u_{\nu,\kappa}(m,n)$ be the number of threshold functions $g$ on $E_m\times E_n$ with $|T(g)|=3$ such that $g(0,0)=\nu$ ($\nu\in\{0,1\}$) and
a minimum teaching set of $g$ consists of $\kappa$ zeros and $3-\kappa$ ones ($\kappa\in\{1,2\}$).
The number $u_{0,1}(m,n)$ enumerates so-called \emph{unstable threhold functions}~\cite{Alekseyev2010}:

\begin{lemma}[\cite{Alekseyev2010}] \label{lemma:unstable}
$$ u_{0,1}(m,n) = 2\cdot f_1(\tfrac{m}{2},\tfrac{n}{2})+2 - s(m,n), $$
where
$$s(m,n) = \sum_{\substack{0<i<m\\ 0<j<n\\ \gcd(i,j)=1}} 1,$$
which can be also expressed as
$$s(m,n) = \frac{1}{4}\left( f_1(m,n) - f_1(m-1,n) - f_1(m,n-1) + f_1(m-1,n-1) \right) - 1.$$
\end{lemma}

\begin{theorem}
$$
\begin{array}{lllll}
u_{0,1}(m,n) &=& u_{1,2}(m,n) &=& 2\cdot f_1(\tfrac{m}{2},\tfrac{n}{2})+2 - s(m,n),\\
u_{0,2}(m,n) &=& u_{2,1}(m,n) &=& f_2(m,n) + 2 - 2\cdot f_1(\tfrac{m}{2},\tfrac{n}{2}) + s(m,n).
\end{array}
$$
Furthermore, for any $\nu\in\{0,1\}$, $\kappa\in\{1,2\}$, and $m\leq n$, we have
$$u_{\nu,\kappa}(m,n) = \frac{3}{4\pi^2}(mn)^2 + O(mn^2).$$
\end{theorem}

\begin{proof} Trivially, we have $u_{0,1}(m,n) + u_{0,2}(m,n) + u_{1,1}(m,n) + u_{1,2}(m,n) = t_3(m,n)$.
Furthermore, the bijection $g\mapsto 1-g$ implies that $u_{\nu,\kappa}(m,n) = u_{1-\nu,3-\kappa}(m,n)$ and thus we can focus only on the case $\nu=0$,
for which $u_{0,1}(m,n) + u_{0,2}(m,n) = \tfrac{1}{2}t_3(m,n)$.
The exact formulae now easily follow from Theorem~\ref{th_t3t4} and Lemma~\ref{lemma:unstable}. To obtain the asymptotics, we use Lemma~\ref{lemma_fqmn}
and notice that $s(m,n) = O(mn)$.
\end{proof}

\section{Special arrangements of lines}

\subsection{Partition of the plane}

For a threshold function $g\in{\cal T}(m,n)$, all vectors $(a_0, a_1, a_2)\in\mathbb{R}^3$, where  $a_0, a_1, a_2$ are coefficients of its separating line,
form a polyhedral cone defined by the following system of linear inequalities:
\begin{equation}
\begin{cases}
	a_1 x_1 + a_2 x_2 \le a_0 & \mbox{for each $(x_1,x_2)\in M_0(g)$}, \\
	a_1 x_1 + a_2 x_2 >   a_0 & \mbox{for each $(x_1,x_2)\in M_1(g)$}.
\end{cases}
\label{eq:Kf}
\end{equation}
Furthermore, a minimal teaching set $T(g)$ consists of the points from $E_m\times E_n$
that correspond to irredundant inequalities in \eqref{eq:Kf}.
Thus, there is a bijection of the set ${\cal T}(m,n)$ into the set of cones in the partition of the space of parameters $\{ (a_0, a_1, a_2)\in\mathbb{R}^3 \}$
by all the planes $a_1 x_1 + a_2 x_2 = a_0$, where $(x_1,x_2)\in E_m\times E_n\setminus \{(0,0)\}$.
Moreover, the planes that form the boundary of each of these cones correspond to the points in $T(g)$.
This construction is well known in the threshold logic~\cite{ShevchenkoZolotykh1998,ZolotykhShevchenko1999}.

\begin{figure}
\begin{center}

\psset{xunit=1.75cm,yunit=1.75cm}
\begin{pspicture}(-2,-2.1)(2,2)

  \psline[arrows=->,linestyle=dashed](-2,0)(2.1,0)
  \psline[arrows=->,linestyle=dashed](0,-2)(0,2.05)
  \rput[lb](2.1,0.015){$a_1$}
  \rput[l](0,2.05){~$a_2$~}

\psline(-1,2)(2,-1)
\psline(-2,1)(2,1)
\psline(-0.5,2)(1.5,-2)

\psline(-2,0.5)(2,0.5)
\psline(-2,1.5)(2,-0.5)
\psline(-1.5,2)(2,-1.5)

\psline(0.5,2)(0.5,-2)
\psline(1,2)(1,-2)

\rput[tr](1,-0.055){$1$~}
\rput[tr](0.5,-0.055){$\frac{1}{2}$~}
\rput[tr](0,-0.055){$0$~}

\rput[rt](0,0.95){$1$~}
\rput[rt](0,0.45){$\frac{1}{2}$~}

\end{pspicture}

\caption{The partition of the plane $\{ (a_1, a_2)\in\mathbb{R}^2 \}$ by the lines $a_1 x_1 + a_2 x_2 = 1$, where $(x_1,x_2)\in E_3\times E_3\setminus \{(0,0)\}$.
There are $c(3,3)=29$ cells, $c_3(3,3)=20$ generalized 3-polygons, $c_4(3,3)=9$ generalized 4-polygons, $e(3,3)=43$ edges, and $v(3,3)=15$ vertices in this partition.}
\label{Fig3}

\end{center}
\end{figure}

For $\nu\in\{0,1\}$, let ${\cal T}_{\nu}(m,n) = \{g\in {\cal T}(m,n):~ g(0,0)=\nu \}$.
The mapping $g \mapsto 1-g$ represents a bijection between the sets ${\cal T}_0(m,n)$ and ${\cal T}_1(m,n)$,
for which the teaching sets are invariant.

Without loss of generality, for $g\in{\cal T}_0(m,n)$, we can assume that $a_0=1$.
In this case the points $(a_1, a_2)\in\mathbb{R}^2$ such that the line $a_1 x_1 + a_2 x_2 = 1$ is separating for $g$ represent the solutions
to the following system of linear inequalities:
$$
\begin{cases}
	a_1 x_1 + a_2 x_2 \le 1 & \mbox{for all $(x_1,x_2)\in M_0(g)$}, \\
	a_1 x_1 + a_2 x_2 >   1 & \mbox{for all $(x_1,x_2)\in M_1(g)$}.
\end{cases}
$$
So we have the bijection of the set ${\cal T}_0(m,n)$ into the set of all polygonal cells in the partition of the plane $\{ (a_1, a_2)\in\mathbb{R}^2 \}$
by the lines $a_1 x_1 + a_2 x_2 = 1$, where $(x_1,x_2)\in E_m\times E_n\setminus \{(0,0)\}$ (see\,Fig.~\ref{Fig3}).

Let $c(m,n)$, $e(m,n)$, $v(m,n)$ be respectively the number of cells, edges,
and vertices (i.e., intersection points) in this partition.
We call a convex polygon (possibly unbounded) by a \emph{generalized $k$-polygon} if it can be obtained as the intersection of
an $k$-faced polyhedral cone with a plane that does not contain the cone vertex.
Every unbounded generalized $k$-polygon representing a cell in the partition has two parallel or two non-parallel \emph{infinite edges} (i.e., rays).
In the former case, the polygon has $k-1$ vertices; in the latter case, it has $k-2$ vertices.

\begin{theorem}\label{th_partition1}
The cells in the partition of the plane $\{ (a_1, a_2)\in\mathbb{R}^2 \}$ by the lines $a_1x_1 + a_2x_2 = 1$, where
$(x_1,x_2)\in E_m\times E_n$, are only generalized $3$- and $4$-polygons.
The number of such cells is, respectively,
\begin{equation}\label{eq_v3v4}
\begin{array}{lllllll}
c_3(m,n) &=& \frac{1}{2}t_3(m,n) &=& f_2(m,n) + 4 &=& \frac{3}{2\pi^2} m^2n^2 + O(mn^2), \\
c_4(m,n) &=& \frac{1}{2}t_4(m,n) &=& \frac{1}{2}f_1(m,n) - f_2(m,n) - 3 &=& \frac{3}{2\pi^2} m^2n^2 + O(mn^2),
\end{array}
\end{equation}
which imply that
\begin{equation}\label{eq_v}
c(m,n) = c_3(m,n)+c_4(m,n) = \frac{1}{2} f_1(m,n) + 1 = \frac{3}{\pi^2} m^2n^2 + O(mn^2).
\end{equation}
Moreover,
\begin{equation}
e(m,n) = f_1(m,n) -\frac{1}{2} f_2(m,n) - s(m,n) - 2 = \frac{21}{4\pi^2} m^2n^2 + O(mn^2),
\label{eq:edges_plane}
\end{equation}
\begin{equation}
v(m,n) = \frac{1}{2} f_1(m,n) -\frac{1}{2} f_2(m,n) - s(m,n) - 2 = \frac{9}{4\pi^2} m^2n^2 + O(mn^2),
\label{eq:points_plane}
\end{equation}
where $s(m,n)$ is defined in Lemma~\ref{lemma:unstable}.
Everywhere above the asymptotics holds for $m\le n$.
\end{theorem}

\begin{proof}
The number of cells is $c(m,n)=|{\cal T}_0(m,n)| = \frac{1}{2} t(m,n)$.
Among them there are $c_3(m,n)=\frac{1}{2}t_3(m,n)$ generalized $3$-polygons and $c_4(m,n)=\frac{1}{2}t_4(m,n)$ generalized $4$-polygons,
since the mapping $g \mapsto 1-g$ is a bijection between ${\cal T}_0(m,n)$ and ${\cal T}_1(m,n)$,
for which the teaching sets are invariant.
To obtain \eqref{eq_v3v4} and \eqref{eq_v} it remains to apply Theorem \ref{th_t3t4} and Lemma \ref{lemma_fqmn}.

Let $v_{\infty}(m,n)$ be the number of \emph{infinite vertices} (i.e., families of parallel lines) in the partition,
which also equals the total number of \emph{infinitely-distant edges} in the unbounded generalized polygons.
Each family of parallel lines is defined by the slope, which may be zero (for the horizonal lines), infinite (for the vertical lines),
or represent an irreducible fraction $\tfrac{p}{q}$ with $1\leq p\leq m-1$ and $1\leq q\leq n-1$. Since the number of such fractions is given by $s(m,n)$,
we have $v_{\infty}(m,n) = s(m,n) + 2$.

Since $3c_3(m,n) + 4c_4(m,n)$ gives twice the number of edges including infinitely-distant ones, we have
$
3c_3(m,n) + 4c_4(m,n) = 2e(m, n) + 2v_{\infty}(m,n),
$
which together with \eqref{eq_v3v4} implies \eqref{eq:edges_plane}.

To find the number of vertices, we apply Euler characteristic for the plane:
$
v(m,n) - e(m,n) + c(m,n) = 1
$
and use \eqref{eq_v} and \eqref{eq:edges_plane} to obtain \eqref{eq:points_plane}.
\end{proof}

\subsection{Partition of the triangle}

Now we consider the triangle with vertices $(0,0)$, $(1,0)$, ($0,1)$ in the plane
$\{ (a_1, a_2)\in\mathbb{R}^2 \}$ and its partition by the lines $a_1x_1 + a_2x_2 = 1$, where
$(x_1,x_2)\in\{1,2,\dots,m\}\times\{1,2,\dots,n\}$ (Fig.\,\ref{Fig4}).
Let $c^{\triangle}(m,n)$, $e^{\triangle}(m,n)$, $v^{\triangle}(m,n)$ be respectively
the number of cells, edges, and vertices in this partition.

\begin{figure}
\begin{center}

\psset{xunit=7.5cm,yunit=7.5cm}
\begin{pspicture}(0,-0.1)(1,1)

  \psline[arrows=->](1.1,0)
  \psline[arrows=->](0,1.05)
  \rput[lb](1.1,0.015){$a_1$}
  \rput[l](0,1.05){~$a_2$~}

\psline(0,1.00000)(1,0)\psline(0,1.00000)(0.5,0)\psline(0,1.00000)(0.333333,0)\psline(0,1.00000)(0.25,0
\psline(0,0.50000)(1,0)\psline(0,0.50000)(0.5,0)\psline(0,0.50000)(0.333333,0)\psline(0,0.50000)(0.25,0
\psline(0,0.33333)(1,0)\psline(0,0.33333)(0.5,0)\psline(0,0.33333)(0.333333,0)\psline(0,0.33333)(0.25,0
\psline(0,0.25000)(1,0)\psline(0,0.25000)(0.5,0)\psline(0,0.25000)(0.333333,0)\psline(0,0.25000)(0.25,0

\rput[tc](1,-0.035){$1$}
\rput[tc](0.5,-0.045){$\frac{1}{2}$}
\rput[tc](0.33333,-0.045){$\frac{1}{3}$}
\rput[tc](0.25,-0.045){$\frac{1}{4}$}
\rput[tc](0,-0.035){$0$}
\rput[r](-0.02,1){$1$}
\rput[r](-0.02,0.5){$\frac{1}{2}$}
\rput[r](-0.02,0.33333){$\frac{1}{3}$}
\rput[r](-0.02,0.25){$\frac{1}{4}$}

\end{pspicture}

\caption{The partition of the triangle by the lines $a_1 x_1 + a_2 x_2 = 1$, where $(x_1,x_2)\in \{1,2,3,4\}\times\{1,2,3,4\}$.
There are $c^{\triangle}(4,4)=47$ cells, $c^{\triangle}_3(4,4)=33$ triangles, $c^{\triangle}_4(4,4)=14$ quadrilaterals, $e^{\triangle}(4,4)=82$ edges,
and $v^{\triangle}(4,4)=36$ vertices in this partition.}
\label{Fig4}

\end{center}
\end{figure}

\begin{theorem}
Every cell in the partition of the triangle with vertices $(0,0)$, $(1,0)$, $(0,1)$ by the lines $a_1x_1 + a_2x_2 = 1$, where
$(x_1,x_2)\in \{1,2,\dots,m\}\times\{1,2,\dots,n\}$, $m\ge 2$, $n\ge 2$, there is either a triangle or a quadrilateral.
Moreover, the number of triangles and quadrilaterals is given by the following formulae:
$$
\begin{array}{lllll}
c^{\triangle}_3(m,n) & = & \frac{1}{2} f_2(m,n) + m + n + 1 & = & \frac{3}{4\pi^2} m^2n^2 + O(mn^2), \\
c^{\triangle}_4(m,n) & = & \frac{1}{4} f_1(m,n) - \frac{1}{2} f_2(m,n) - \frac{m}{2} - \frac{n}{2} - 1 & = & \frac{3}{4\pi^2} m^2n^2 + O(mn^2),
\end{array}
$$
which imply that
$$
c^{\triangle}(m,n) = c^{\triangle}_3(m,n) + c^{\triangle}_4(m,n) = \frac{1}{4} f_1(m,n) +\frac{m}{2} + \frac{n}{2} = \frac{3}{2\pi^2} m^2n^2 + O(mn^2).
$$
Moreover,
\begin{equation}
e^{\triangle}(m,n) = \frac{1}{2} f_1(m,n) -\frac{1}{4} f_2(m,n) + m + n = \frac{21}{8\pi^2} m^2n^2 + O(mn^2),
\label{eq:edges_triangle}
\end{equation}
\begin{equation}
v^{\triangle}(m,n) = \frac{1}{4} f_1(m,n) -\frac{1}{4} f_2(m,n) + \frac{m}{2} + \frac{n}{2} + 1 = \frac{9}{8\pi^2} m^2n^2 + O(mn^2).
\label{eq:points_triangle}
\end{equation}
Everywhere above the asymptotics holds for $m\le n$.
\end{theorem}

\begin{proof}
We notice that all cells incident to the axes are triangular and use Theorem~\ref{th_partition1} to obtain
$$
\begin{array}{lllll}
c^{\triangle}_3(m,n) & = & \frac{1}{4} t_3(m,n) + m + n - 1 & = & \frac{1}{2} f_2(m,n) + m + n + 1, \\
c^{\triangle}_4(m,n) & = & \frac{1}{4} t_4(m,n) - \frac{1}{2}(m + n - 1) & = & \frac{1}{4} f_1(m,n) - \frac{1}{2} f_2(m,n) - \frac{m}{2} - \frac{n}{2} - 1.
\end{array}
$$
The number $e^{\triangle}(m,n)$ of edges satisfies the equality:
$
2e^{\triangle}(m,n) = 3c^{\triangle}_3(m,n) + 4c^{\triangle}_4(m,n) + m + n + 1,
$
which implies \eqref{eq:edges_triangle}.
Now we use Euler characteristic for the triangle:
$
v^{\triangle}(m,n) - e^{\triangle}(m,n) + c^{\triangle}(m,n) = 1
$
to obtain \eqref{eq:points_triangle}.
\end{proof}

\section*{Acknowledgments}
The first author was supported by the National Science Foundation under the grant No. IIS-1253614.

\bibliographystyle{siam}