TITLE: Solve $\frac {2 \tan x}{1-\tan^2x} = \sin^22x$
QUESTION [1 upvotes]: How would I solve this trigonometric equation?
$$\frac {2 \tan x}{1-\tan^2x} = \sin^22x$$
I got to this stage: $$\frac{\sin2x}{\cos2x} = \sin^22x$$
Is it a dead end?

REPLY [2 votes]: Try to rewrite it in the following way. $$0=\sin^2(2x)-\frac{\sin(2x)}{\cos(2x)}$$
$$0 = \sin(2x) \cdot \left[\sin(2x)-\frac{1}{\cos(2x)}\right]$$
$$0= \sin(2x) \cdot \frac{\sin(2x)\cdot \cos(2x)-1}{\cos(2x)}$$
Then use $\sin(2x) \cdot \cos(2x) = \frac{\sin(4x)}{2}$.


TITLE: Smooth Morse function from Forman's discrete Morse function
QUESTION [9 upvotes]: Let $M$ be a smooth manifold and $K$ a triangulation of $M$, so $K$ is a regular CW-complex and in particular a simplicial complex. Assume that $M$ is compact so $K$ is finite. Let $f\colon K \to \mathbb{R}$ be a discrete Morse function (in the sense of Forman). Is is possible to define a smooth Morse function $f'\colon M \to \mathbb{R}$ with the same critical points as $f$ (and satisfying a correspondence between the indexes of the critical points)? Is it possible to do it in "an algorithmic way" (I mean that the proof is constructive)?
As far as I know, the converse was addressed by Gallais and Benedetti, am I right?
I apologize in advance if the questions are to vague or the answers are well-known. Thanks in advance for your time.

REPLY [9 votes]: You can do the next best think. To a  Forman-Morse function $f$ one can associate  a flow on the manifold whose stationary points are precisely  the barycenters  of the faces  of your simplicial decomposition.    The Conley index of the barycenter of a critical face has the homotopy type of a sphere of the dimension of that face. The Conley index of the barycenter of a non-critical face is homotopically trivial.
Additionally, one can construct a continuous function $\tilde{f}$ on the manifold that decreases along the trajectories of this flow and whose value at a barycenter is equal to the value of $f$ on the corresponding face. As  Mike Miller correctly pointed out,  a critical face is filled out by the  trajectories exiting the barycenter.
For details  see Chapter 11 of this paper.  The faces of the barycentric subdivision of your simplicial complex are invariant  sets of this flow, and on  such a face the flow is depicted in Figure 2, p.16 of the above paper.
It took me a while to realize that in Morse theory  the gradient flow associated to a Morse function is more important than the function itself.  The function plays a sort of accounting role and  the Morse condition  restricts the nature of the stationary points of the gradient flows.
Remark  A while ago I asked this question on MathOverflow that is related to the abundance of discrete Morse functions. They are extremely rare as opposed to the  usual smooth Morse functions that are generic.


TITLE: Is there a non-abelian group without non-trivial core-free subgroup?
QUESTION [2 upvotes]: A subgroup $H \subset G$ is called core-free if for any normal subgroup $N \triangleleft G$ then $N \subset H$ implies $N=1$.
Of course, every proper subgroup of $S$ simple is core-free, and every core-free subgroup of $A$ abelian is trivial.
Question: Is there a non-abelian group without non-trivial core-free subgroup?
If necessary, we can assume all the groups to be finite.

REPLY [1 votes]: Yes.
Assume that $G$ is a finite group wihtout non-trivial core-free subgroup.   Let $A_1, \dots , A_r$ be the atoms of the subgroup lattice $\mathcal{L}(G)$. Then by assumption, $\forall i, A_i \triangleleft G$. If moreover $\mathcal{L}(G)$ is atomistic then every subgroup of $G$ is normal, i.e. $G$ is a Dedekind group. A non-abelian Dedekind group is called a Hamiltonian group. We see that any Hamiltonian group has the expected property. The first example is the quaternion group.
Bonus question: Is there a non-Dedekind group without non-trivial core-free subgroup?


TITLE: How do I find if the series $\sum\frac{2^n}{n^2}$ converges?
QUESTION [2 upvotes]: How do I find if the series
$$\sum_{n \ge 1}\frac{2^n}{n^2}$$
converges?
I know it diverges but I'm trying to figure out the steps. I tried applying l'hoptital's rule for the divergence test but the result keeps getting bigger... I'm sure there is some simple trick that I'm forgetting but it's driving me nuts. Someone please explain the steps for breaking this one down.

REPLY [1 votes]: What about simply the $\;n\,-$ th root test?:
$$\sqrt[n]{\frac{2^n}{n^2}}=\frac2{\left(\sqrt[n]n\right)^2}\xrightarrow[n\to\infty]{}2>1$$
and thus the series diverges.

REPLY [0 votes]: Note $2^n > n^2$ for $n \geq 5$ by induction. You need to show $2^n > 2n+1$ for the inductive step; to show this, you can use induction again and here it suffices to show $2^n > 2$ which is trivial.
Then $$\sum_{n \geq 1} \frac{2^n}{n^2} > \sum_{n \geq 5} \frac{2^n}{n^2}  > \sum_{n \geq 5} 1 \xrightarrow[n \to \infty]\ \infty$$
Asymptotically, $n^2 = o(2^n)$ so not only does the series diverge, but it really diverges.


text:
\begin{document}

\maketitle

\begin{abstract}
We prove a strong form of model completenes for expansions of the field of real numbers by (the real and imaginary parts of) the modular function J, by the modular forms $E_4$ and $E_6$ and quasimodular form $E_2$ defined in the usual fundamental domain, and the restricted sine function and the (unrestricted) exponential function. This is done using ideas of Peterzil and Starchenko's paper \cite{peterzil-starchenko-wp2004} on the uniform definability of $\wp$ function in $\mathbb{R}_{\mathit{an}}$ (and of the modular function $J$). In the conclusion we pose some open problems related to this work.

\textbf{Mathematical Subject Classification (2010)}. Primary: 03C10. Secondary: 03C64, 11F03, 14H52, 14K20, 33E05.

\textbf{Keywords:} model completeness, Weierstrass systems, elliptic functions, Siegel modular function, modular forms, quasimodular forms, exponential function, o-minimality.

\end{abstract}

\section{Introduction}

We prove a strong form of model completeness for some expansions of the field of real numbers by modular functions and forms and also by universal families of elliptic functions.

This type of result was first proved for expansions of the field of real numbers by real analytic functions restricted to the product of intervals by Jan Denef and Lou van den Dries in \cite{denef-vddries1988} (this structure is now called $\mathbb{R}_{\mathit{an}}$), by Lou van den Dries for expansions by the restricted sine and exponential functions in \cite{vandendries1988} and by the author for expansions by restricted Weierstrass $\wp$ and abelian functions in \cite{bianconi1991}. These results depend, among other things, on the fact that the functions used in the definition of the structures are analytic at the boundary (or at infinity). A major brakthrough came in 1991 when Alex Wilkie showed the model completeness of the expansion of the field of real numbers by the unrestricted exponential function (which is not analytic at infinity) in \cite{wilkie1996}. Motivated by this result, but using a different technique, Lou van den Dries, Angus Macintyre and David Marker proved in \cite{vandendries-etc-1996} the model completeness of $\mathbb{R}_{\mathit{an,exp}}$, the expansion of $\mathbb{R}_{\mathit{an}}$ by the unrestricted exponential function. These results were used to conclude the o-minimality of such structures.

In 2004, Ya'acov Peterzil and Sergei Starchenko showed in \cite{peterzil-starchenko-wp2004} the remarkable result that the Weierstrass $\wp$ function, as a function of the variables $z$ and $\tau$ (the parameter), is definable in $\mathbb{R}_{\mathit{an,exp}}$ (but not in $\mathbb{R}_{\mathit{an}}$). In their paper they also have shown that the modular function $J$ is also definable in $\mathbb{R}_{\mathit{an}}$. Their results (and some others discussed in the Section \textit{Concluding Remarks}) have led to the question about model completeness of the expansion by such functions. We prove here the (strongly) model completeness of expansions of the field of real numbers by including in the language finitely many function symbols, containing modular functions and forms and the unrestricted exponential function.

The strategy of our proof starts with the ideas of their paper, transforming the problem to a reduct of $\mathbb{R}_{\mathit{an}}$ (via Eisenstein series) and then we use the ideas from \cite{vandendries-etc-1996} to introduce the unrestricted exponential function in order to obtain the model completeness for expansions by modular functions and forms defined in the fundamental domain $\{\tau\in\mathbb{C}:-1/2\leq\mathfrak{Re}(\tau)<1/2$ and $|\tau|\geq 1\}$.

This work is organised as follows. The following section contains the general elimination of quantifies and model completeness results to be used. In the next section we present the main results on the modular function $J$ and on quasimodular forms. In the final section on concluding remarks we comment on the problem of noneffectiveness of our proofs and present some open problems related to the questions treated in this work. We have included in the bibliography the \textit{Mathematical Reviews} number of the references for easy search.

\textbf{Notation.} We denote by $\mathbb{Z}$ the ring of rational integers, $\mathbb{N}$ the set of nonnegative integers, $\mathbb{R}$ the field of real numbers, $\mathbb{C}$ the field of complex numbers; $\mathfrak{Re}(z)$ and $\mathfrak{Im}(z)$ denote the real and imaginary parts of $z$, the letter $i$ denotes $\sqrt{-1}$,  and $\bar{x}$ denotes the tuple $(x_1,\dots,x_n)$ for some unspecified $n$. Other notations are explained in the text.

\section{Strong Model Completeness Results}

The theory $T$ of a structure $M$ is called \textbf{strongly model complete} if for each formula $\varphi(\bar{x})$ there is a quantifier free formula $\psi(\bar{x},\bar{y})$ such that
$$
T\vdash\forall \bar{x}\,[\varphi(\bar{x})\leftrightarrow\exists\bar{y}\,\psi(\bar{x},\bar{y})]
$$
and $T\vdash\forall\bar{x}\forall\bar{y}\forall\bar{z}(\psi(\bar{x},\bar{y})\wedge\psi(\bar{x},\bar{z})\to\bar{y}=\bar{z})$. That is, each formula is equivalent to an existential formula witnessed by a unique element (for each tuple $\bar{x}$).

A set in a structure is called \textbf{strongly definable} if it is defined by such an existential formula.

We first recall a general strong model completeness result for Weierstrass systems with the (unrestricted) exponential functions and then show the particular cases of modular functions and modular forms.

\subsection{Weierstrass Systems}

In this section $K$ stands for the field of real or of complex numbers, $\mathbb{R}$ or $\mathbb{C}$, $K[x_1,\dots,x_n]$ for the ring of polynomials with coefficients in $K$ and the shown variables $x_1$, \dots, $x_n$, $K[[x_1,\dots,x_n]]$ the ring of (formal) power series over $K$ and $K\{x_1,\dots,x_n\}$ its subring of power series converging in some polydisk centred at $\mathbf{0}\in K\sp{n}$. We usually denote $\bar{x}_{(n)}$, or simply $\bar{x}$ when the subscript $n$ is clear from the context, for the $n$-tuple of variables $x_1$, \dots, $x_n$.

\begin{definition}\rm
A \textit{Convergent Weierstrass system, W-system} for short, over $K$ is a family of
rings $W=(K\lfloor x_1,\dots,x_n\rfloor)_{n\in\mathbb{N}}$ satisfying the following conditions, for all $n\in\mathbb{N}$:
\begin{itemize}
\item[W1]
$K[\bar{x}]\subseteq K\lfloor\bar{x}\rfloor \subseteq K[[\bar{x}]]$, $K\lfloor\bar{x}\rfloor$ is closed under the action of the permutation on the variables and if $m>n$, then $K\lfloor\bar{x}_{(n)}\rfloor = K\lfloor\bar{x}_{(m)}\rfloor\cap K[[\bar{x}_{(n)}]]$;
\item[W2]
if $f\in K\lfloor\bar{x}\rfloor$ is invertible in $K[[\bar{x}]]$ then its inverse belongs to $K\lfloor\bar{x}\rfloor$;
\item[W3]
\textit{(Weierstrass Division)}
if $f\in K\lfloor\bar{x}_{(n+1)}\rfloor$ and $f(\mathbf{0},x_{n+1})\in K[[x_{n+1}]]$ is nonzero of order $d\in\mathbb{N}$ (that is, $f(\mathbf{0},x_{n+1})= \sum_{i=d}\sp{\infty}c_ix_{n+1}\sp{i}$, with $c_d\neq 0$) then for all $g\in K\lfloor\bar{x}_{(n+1)}\rfloor$, there are $Q\in K\lfloor\bar{x}_{(n+1)}\rfloor$ and
$R_i\in K\lfloor\bar{x}_{(n)}\rfloor$, $0\leq i\leq d-1$, such that $g(\bar{x}_{(n+1)})=Q(\bar{x}_{(n+1)})f(\bar{x}_{(n+1)})+\sum_{i=0}\sp{d-1}R_i(\bar{x}_{(n)})x_{n+1}\sp{i}$.
\item[W4]
$K\lfloor\bar{x}_{(n)}\rfloor\subseteq K\{\bar{x}_{(n)}\}$ and if the element $f\in K\lfloor\bar{x}_{(n)}\rfloor$ converges on the polydisk $D_{\varepsilon}(0)=\{\bar{x}\in \mathbb{C}\sp{n}:|x_1|<\varepsilon,\dots, |x_n|<\varepsilon\}$ then for each $a\in D_{\varepsilon}(0)\cap K\sp{n}$, the series
$$
f_a(\bar{x}_{(n)})=f(a+\bar{x}_{(n)})=\sum_{\mathbf{i}\in\mathbb{N}}\frac{\partial\sp{\mathbf{i}} f\phantom{n}}{\partial \bar{x}_{(n)}\sp{\mathbf{i}}}(a)\frac{\bar{x}_{(n)}\sp{\mathbf{i}}}{\mathbf{i}!}
$$
also belongs to $K\lfloor{\bar{x}_{(n)}}\rfloor$, where, as usual, if $\mathbf{i}=(i_1,\dots,i_n)\in\mathbb{N}\sp{n}$, then $\mathbf{i}!=i_1!\dots i_n!$, $\bar{x}_{(n)}\sp{\mathbf{i}}=x_1\sp{i_1}\dots x_n\sp{i_n}$ and
$$
\frac{\partial\sp{\mathbf{i}}f\phantom{n}}{\partial \bar{x}_{(n)}\sp{\mathbf{i}}}=\frac{\partial\sp{i_1+\dots+i_n}f}{\partial x_1\sp{i_1}\dots\partial x_n\sp{i_n}}.
$$
\end{itemize}
\end{definition}

Observe that in any W-system, $\mathbb{R}\lfloor\bar{x}_{(0)}\rfloor$ is just the real field $\mathbb{R}$.

Given a W-system $\mathcal{W}=(\mathbb{R}\lfloor \bar{x}_{(n)}\rfloor)_{n\geq 0}$, we define for each $n\geq 1$ the ring $\mathbb{R}_W\{\bar{x}_{(n)}\}$ containing all $f\in\mathbb{R}[[\bar{x}_{(n)}]]$ which converge in a neighbourhood of $I\sp{n}$ and for all $a\in I\sp{n}$ the translated series $f_a$ belongs to $\mathbb{R}\lfloor \bar{x}_{(n)}\rfloor$, where $I$ is the interval $[-1,1]$.

Let $L_{W}$ be the first order language which has the usual symbols for the theory of ordered fields ($+$, $\cdot$, $-$, $<$, ${\,}\sp{-1}$, 0, 1) and also for each $n\geq 1$ and each $f\in\mathbb{R}_W\{\bar{x}_{(n)}\}$ a function symbol $F$.

We make $\mathbb{R}$ into an $L_W$-structure interpreting the symbols of $L_W$ as follows:
\begin{itemize}
\item
the symbols $+$, $\cdot$, $-$, $<$, ${\,}\sp{-1}$, 0, 1 have the usual interpretation, with the covention that $0\sp{-1}=0$;
\item
if $F$ corresponds to the series $f\in\mathbb{R}_W\{\bar{x}_{(n)}\}$, then the interpretation $\tilde{F}$ of $F$ is
$$
\tilde{F}(\bar{x})=
\left\{
\begin{array}{lcl}
f(\bar{x}) & \mbox{if} & \bar{x}\in I\sp{n},\\
0 & & \mbox{otherwise.}
\end{array}
\right.
$$
\end{itemize}

We denote $\mathcal{R}_W$ for such structure.

In \cite[Section 4]{denef-vddries1988}  it was proven a quantifier elimination result for the W-system of all convergent power series. The proof also works for any W-system and the details of such proof can be found in \cite[Section 2]{bianconi1991} (with the appropriate modifications).

\begin{theorem}\label{QE-W-system}
The theory of $\mathcal{R}_W$ admits quantifier elimination in the language $L_W$.
\end{theorem}

The next theorem is based on \cite[Theorem 3.12]{bianconi1991} which gives a criterion for strong model completeness of expansions of the field of the real numbers by restricted analytic functions. The conditions imply that the strongly definable complex analytic functions form a Weierstrass system, permitting the use of the results above. (We say that a complex function is strongly definable in the structure if its real and imaginary parts are strongly definable.)

\begin{theorem}\label{model-completeness-W-system}
Let $\hat{R}=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<,(F_{\lambda})_{\lambda\in\Lambda}\rangle$ be an expansion of the field of real numbers, where for each $\lambda\in\Lambda$, $F_{\lambda}$ is the restriction to a compact polyinterval $D_{\lambda}\subseteq\mathbb{R}\sp{n_{\lambda}}$ of a real analytic function whose domain contains $D_{\lambda}$(and defined as zero outside $D_{\lambda}$), such that there exists a complex analytic function $g_{\lambda}$ defined in a neighbourhood of a polydisk $\Delta_{\lambda}\supseteq D_{\lambda}$ and such that
\begin{enumerate}
\item
$g_{\lambda}$ is strongly definable in $\hat{R}$ and the restriction of $g_{\lambda}$ to $D_{\lambda}$ coincides with $F_{\lambda}$ restricted to the same set;
\item
for each $a\in\Delta_{\lambda}$ there exists a compact polydisk $\Delta$ centred at $a$ and contained in the domain of $g_{\lambda}$, such that all the partial derivatives of the restriction of $g_{\lambda}$ to $\Delta$ are strongly definable in $\hat{R}$.
\end{enumerate}
Under these hypotheses, the theory of $\hat{R}$ is strongly model complete.
\end{theorem}

\subsection{Inclusion of the Exponential Function}

We introduce the full exponential function in order to obtain the main results of this work.

The following theorem is essentially contained in \cite{vandendries-etc-1996}, adapted to the context of W-systems. The authors describe generalised power series fields as models of $\mathbb{R}_{\mathit{an}}$ and use Shoenfield's criterion \cite{shoenfield1971} to prove quantifier elimination. Our proof is the same as in \cite{vandendries-etc-1996}, with the obvious modifications, so we omit it.

\begin{theorem}
Suppose that some restriction of $\exp$ and $\log$ belong to the W-system $\mathcal{W}$. Then
$\hat{R}=\langle \mathbb{R},\,\mathit{constants},+,\cdot,(\cdot)\sp{-1},<,(F_{w})_{w\in W},\exp,\log\rangle$ admits quantifier elimination, where $\exp$ and $\log$ denote the unrestricted exponential and logarithm functions with the convention that $\log x=0$ for $x\leq 0$.
\end{theorem}

Now we can state the main result.

\begin{theorem}
Let $\hat{R}$ be the structure described in Theorem \ref{model-completeness-W-system}. We assume that the functions
$$
e(x)=
\left\{
\begin{array}{lcl}
\exp x & \mbox{if} & 0\leq x\leq 1,\\
0 & & \mbox{otherwise};
\end{array}
\right.
$$
$$
s(x)=
\left\{
\begin{array}{lcl}
\sin x & \mbox{if} & 0\leq x\leq \pi,\\
0 & & \mbox{otherwise},
\end{array}
\right.
$$
have representing function symbols in its language.
The expansion $\hat{R}_{\mathrm{exp}}$ of $\hat{R}$ by the inclusion of the (unrestricted) exponential function ``$\exp$'' is strongly model complete.
\end{theorem}

\textbf{Proof:}
The proof of the analogous to Theorem \ref{model-completeness-W-system} is obtained by interpreting it in another structure like the one in Theorem \ref{QE-W-system}. We can easily adapt the results in \cite[Sections 2, 3 and 4]{vandendries-etc-1996} to our context to prove that the structure $\mathcal{R}_W$ of Theorem \ref{QE-W-system} expanded by the unrestricted $\exp$ and $\log$ still admits elimination of quantifiers. Since the relevant functions of the structure $\mathcal{R}_W$ are strongly definable in $\hat{R}$, we obtain the desired result.\hspace*{\fill}$\square$

\medskip

In the following sections we use this result to show the model completeness of expansions of the real field by modular functions and forms.

As a side remark, a byproduct of the analysis of the reference \cite{vandendries-etc-1996} we obtain that for any W-system $W$, the models of the theory of $\mathbb{R}_W$ which contain $\mathbb{R}$ as a subfield are isomorphic to reducts of the models of $\mathbb{R}_{\mathit{an}}$.

\section{Modular Functions and Forms}

We present below some examples of expansions by modular functions and forms, where we use the general results of the previous section.

\subsection{The Modular Function \textit{J}}

We recall some definitions and results about modular functions (see \cite[Chapters 1 and 2]{schoeneberg1974}).

The modular group is the group $SL(2,\mathbb{Z})$ of $2\times 2$ matrices with integer entries and determinant 1 acting on $\mathbb{H}=\{z\in\mathbb{C}:\mathfrak{Im}(z)>0\}$ by M\"obius transformations
$$
\left(
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right)
\cdot z=\frac{az+b}{cz+d}.
$$
The group is generated by the translation $T(z)=z+1$ and inversion $S(z)=-1/z$ and has a standard fundamental domain $\mathfrak{F}=\{z\in\mathbb{H}$: $|z|\geq 1$ and $-1/2\leq \mathfrak{Re}(z)< 1/2\}$.

A holomorphic (meromorphic) function $f:\mathbb{H}\to\mathbb{C}$ is called a modular function if it satisfies $f(\gamma\cdot z)=f(z)$ for all $\gamma\in SL(2,\mathbb{Z})$. The Siegel Modular Function is the function $J:\mathbb{H}\to\mathbb{C}$ defined as the bijective holomorphic map from $\mathfrak{F}$ onto $\mathbb{C}$ given by the Riemann Mapping Theorem with the conditions that $J(i\infty)=\infty$, $J(i)=1$ and $J(\rho)=0$, where $\rho=(-1+i\sqrt{3})/2$, and extended to the whole $\mathbb{H}$ by the application of all $\gamma\in SL(2,\mathbb{Z})$. All modular functions are rational functions of $J$.

Let $J:\tau\in \mathcal{F}\to J(\tau)\in\mathbb{C}$ be the modular function.
We denote $\tilde{J}:q\in\mathbb{C}\sp{\ast}\to\mathbb{C}$ such that $J(\tau)=\tilde{J}(\exp(2\pi i\tau))$. Since we are considering $q=(u+iv)$ as new variables, and not just a symbol representing $\exp(2\pi i\tau)$, we depart from the usual notation (as in \cite{zagier2008}, for instance) distinguishing $J$ as function of the variable $\tau$ and $\tilde{J}$ as function of the variable $q$.

Notice that $\exp(2\pi i\tau)$ maps the closed strip $\{\tau\in\mathbb{C}:|\mathfrak{Re}(\tau)|\leq 1/2$, $\mathfrak{Im}(\tau)\geq\delta\}$ onto de punctured disk $\{q\in\mathbb{C}:0<|q|\leq\exp(-2\pi\delta)\}$.
This function maps the vertical ray $\{z\in\mathbb{H}:\mathfrak{Re}(z)=-1/2$, $\mathfrak{Im}(z)\geq\delta\}$ onto the segment $\{q\in\mathbb{C}:\mathfrak{Im}(q)=0$, $-\exp(-2\pi\delta)\leq\mathfrak{Re}(q)<0\}$, and the ray $\{z\in\mathbb{H}:\mathfrak{Re}(z)=0$, $\mathfrak{Im}(z)\geq \delta\}$ onto the segment $\{q\in\mathbb{C}:\mathfrak{Im}(q)=0$, $0<\mathfrak{Re}(q)\leq\exp(-2\pi\delta)\}$.
We consider the extension of that mapping sending the point $i\infty$ to the value 0, the limit $\lim_{\tau\to i\infty}\exp(2\pi i\tau)$ (the limit is computed inside the strip).

Kurt Mahler showed in \cite{mahler1969} that the $J(\tau)$, $J'(\tau)$ and $J''(\tau)$ are algebraically independent over $\mathbb{C}(\tau)$ and that $J'''(\tau)$ is a rational function of $J(\tau)$, $J'(\tau)$ and $J''(\tau)$ (see \cite[page 450]{mahler1969}). The derivatives of $j$ are not modular functions, but transform as
$J'(\gamma\cdot \tau)=(c\tau+d)\sp{2}J'(\tau)$ and $J''(\gamma\cdot\tau)=(c\tau+d)\sp{4}J''(\tau)+2(c\tau+d)\sp{3}J'(\tau)$.

In the following theorem $\tilde{J}\sp{(0)}=\tilde{J}$, $\tilde{J}\sp{(1)}=\tilde{J}'$ and $\tilde{J}\sp{(2)}=\tilde{J}''$ (the first and second derivatives of $\tilde{J}$ with respect to the complex variable $q$).

\begin{theorem}\label{model-completeness-J}
The following expansions of the field of the real numbers are strongly model complete, where $q=(u+iv)$ and $|q|=\sqrt{x\sp{2}+y\sp{2}}$:
\begin{enumerate}
\item
$\mathcal{R}_{J_1}=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<,(F\sp{(j)}_n,G\sp{(j)}_n)_{n\in\mathbb{N}, j=0,1,2}\rangle$, where  for each $n\in\mathbb{N}$ and $j=0,1,2$,
$$
F\sp{(j)}_n(q)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(\tilde{J}\sp{(j)}(q)) & \mathrm{if} & |q|\leq 1-\frac{1}{n+1};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
G\sp{(j)}_n(q)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(\tilde{J}\sp{(j)}(q)) & \mathrm{if} & |q|\leq 1-\frac{1}{n+1};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
\item
$\mathcal{R}_{J_2}=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<$, $\mathrm{exp}\lceil_{[0,1]}$, $\mathrm{log}\lceil_{[1,2]}$, $\mathrm{sin}\lceil_{[-\pi,\pi]}$, $\mathrm{cos}\lceil_{[-\pi,\pi]}$, $\arctan\lceil_{[-1,1]}$, $(\tilde{J}\sp{(j)}_{\mathit{re}},\tilde{J}\sp{(j)}_{\mathit{im}})_{j=0,1,2}\rangle$, where for each $j=0,1,2$,
$$
\tilde{J}\sp{(j)}_{\mathit{re}}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(\tilde{J}\sp{(j)}(q)) & \mathrm{if} & |q|\leq 1-\delta;\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
\tilde{J}\sp{(j)}_{\mathit{im}}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(\tilde{J}\sp{(j)}(q)) & \mathrm{if} & |q|\leq 1-\delta;\\
0 &  & \mathrm{otherwise},
\end{array}\right.
$$
where $\delta=\exp(-\pi\sqrt{3})$ and $f\lceil_{[a,b]}$ means the function $f$ restricted to the interval $[a,b]$ and defined as zero elsewhere, for $f$ being the sine, cossine, exponential and arctangent functions.
\end{enumerate}
\end{theorem}

\textbf{Proof:} Let us firstly remark that the choice of the number $\delta$ in item 2 was made in order to include the image, under the change of variables $q=\exp(2\pi i\tau)$, of the smallest vertical strip containing the fundamental domain of the action of $SL(2,\mathbb{Z})$ on $\mathbb{H}$. We also remark that although $\tilde{J}$ has a single pole at the origin, the following argument applies (changing $q\tilde{J}(q)$ for $\tilde{J}(q)$, when necessary).

\medskip

\textbf{1}. Let $\Delta_n=\{q\in\mathbb{C}:|q|\leq 1-1/(n+1)\}$.

Because the first and second derivatives of the function $\tilde{J}$ are present and the third derivative is a rational function of $q$, $\tilde{J}$, $\tilde{J}'$ and $\tilde{J}''$, the only requirement to be proved is the second condition of Theorem \ref{model-completeness-W-system}, for $f_n$ being each one among $F_n\sp{(j)}$, $G_n\sp{(j)}$, $j=0,1,2$:

\begin{quote}
\textit{2.
For each $q\in\Delta_n$ there exists a compact polydisk $\Delta$ centred at $q$ and contained in the domain of $f_n$ such that all the partial derivatives of the restriction of $f_n$ to $\Delta$ are strongly definable in $\hat{R}$.}
\end{quote}

We prove only the case of $F_n\sp{(0)}$  and $G_n\sp{(0)}$, because the other cases are similar and left to the reader.

If $q$ belongs to the interior of $\Delta_n$, let $\epsilon=\mathrm{dist}\,(q,\partial \Delta_n)>0$, the distance from $q$ to the boundary of $\Delta_n$, and let $\Delta(q,\epsilon)$ be the closed disk centred at $q$ and radius $\epsilon$. Using $F\sp{(0)}_n$ and $G_n\sp{(0)}$ restricted to $\Delta(q,\epsilon)$ we can strongly define $\tilde{J}$ restricted to such disk.

If $q\in\partial\Delta_n$, a boundary point of $\Delta_n$, then $q$ belongs to the interior of $\Delta_{n+1}$ and the same argument as above applies, using $F_{n+1}\sp{(0)}$ and $G_{n+1}\sp{(0)}$.

\medskip

\textbf{2.} For this item, we only need to show that the extensions of those functions to larger domains are strongly definable. Here we make use of the modularity property of the function $J(\tau)$ and of its derivatives. The change of variables $q=\exp(2\pi i\tau)$ inverts as $\tau=(\log q)/(2\pi i)$, where we choose the principal branch of $\log$ (that is, $\log q>0$ if $q>0$, both real), because if $\tau=iy$, with $y>0$, then $q=\exp(2\pi i\tau)=\exp(-2\pi y)>0$, a real number. If
$$
\tau'=\frac{a\tau+b}{c\tau+d},
$$
then the corresponding $q'=\exp(2\pi i\tau')$ satisfies
$$
q'=\exp\left[2\pi i\left(\frac{a\log q+2\pi ib}{c\log q+2\pi id}\right)\right].
$$

In particular, if we apply this formula using the transformations $\tau_1=S(\tau)=-1/\tau$, $\tau_2=ST(\tau)=-1/(\tau+1)$ and $\tau_3=ST\sp{-1}(\tau)=-1/(\tau-1)$ (the Figure \ref{fig-Action} below helps to explain these choices), we have:
\begin{enumerate}
\item
the image under $S$ of the (closure of the) fundamental domain $\mathfrak{F}$ is the region inside the cilcle $|\tau|=1$, that is $|\tau|\leq 1$ and also outside the cilcles $|\tau\pm 1|=1$;
\item
the image under of $\bar{\mathfrak{F}}$ $ST$ is $\mathfrak{Re}(\tau)\geq -1/2$, $|\tau+1/3|\geq 1/3$ and $|\tau+1|\leq 1$;
\item
the image of $\bar{\mathfrak{F}}$ under $ST\sp{-1}$ is $\mathfrak{Re}(\tau)\leq 1/2$, $|\tau-1/3|\geq 1/3$ and $|\tau-1|\leq 1$.
\end{enumerate}

We conclude that the union of the images of $\bar{\mathfrak{F}}$ under those maps contains the strip $|\mathfrak{Re}(\tau)|\leq 1/2$, $\mathfrak{Im}(\tau)\geq 1/3$.

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=0.9\textwidth]{Mapping-SL.pdf}
\end{center}
\caption{Action of $S,ST,ST\sp{-1}\in SL(2,\mathbb{Z})$ on the fundamental domain.}
\label{fig-Action}
\end{figure}

Notice that the strip $\{\tau\in\mathbb{H}: |\mathfrak{Re}(\tau)|\leq 1/2$, and $\mathfrak{Im}(\tau)\geq i\sqrt{3}/2\}$ is mapped by $\exp(2\pi i\tau)$ onto the punctured disk $\{q\in\mathbb{C}:0<|q|\leq \exp(-\pi\sqrt{3})\}$ and the strip $\{\tau\in\mathbb{H}: |\mathfrak{Re}(\tau)|\leq 1/2$, and $\mathfrak{Im}(\tau)\geq i/3\}$ is mapped by $\exp(2\pi i\tau)$ onto the punctured disk $\{q\in\mathbb{C}:0<|q|\leq \exp(-\pi/3)\}$.

If $\tau\in\bar{\mathfrak{F}}$ and $\tau_1=S(\tau)=-1/\tau$, $\tau_2=ST(\tau)=-1/(\tau+1)$ and $\tau_3=ST\sp{-1}(\tau)=-1/(\tau-1)$, as above, let $q_j=\exp(2\pi i\tau_j)$, $j=1,2,3$, and $q=\exp(2\pi i\tau)$, then we have
$$
q_1=\exp(2\pi i\tau_1)=\exp\left[-2\pi i\left(\frac{2\pi i}{\log q}\right)\right],
$$
$$
q_2=\exp(2\pi i\tau_2)=\exp\left[-2\pi i\left(\frac{2\pi i}{\log q+2\pi i}\right)\right],
$$
$$
q_3=\exp(2\pi i\tau_3)=\exp\left[-2\pi i\left(\frac{2\pi i}{\log q-2\pi i}\right)\right].
$$

\medskip

From the known formulas $\exp(u+iv)=\exp u\,(\cos v+i\sin v)$ and that $\log (u+iv)=\log \sqrt{u\sp{2}+v\sp{2}}+i\arctan(v/u)$, if $u>0$, $\log (u+iv)=\log \sqrt{u\sp{2}+v\sp{2}}+i[\pi/2-\arctan(u/v)]$, if $u<0$ and $v>0$, and $\log (u+iv)=\log \sqrt{u\sp{2}+v\sp{2}}+i[-\pi/2-\arctan(u/v)]$, if $u,v<0$, we see that (the real and imaginary parts of) the points $q_1$, $q_2$ and $q_3$ are strongly definable from the point $q$.
Observe that we only need the restricted exponential and logarithm to define the points $q_j$, $j=1,2,3$, belonging to the set $\{z\in\mathbb{C}:\exp(-\pi/3)\leq|z|<\exp(-\pi\sqrt{3})\}$.

As the derivatives of the functions $\tilde{J}$, $\tilde{J}'$ and $\tilde{J}''$ are strongly definable in that structure, the only thing to be verified is the second item of Theorem \ref{model-completeness-W-system} quoted above, and again the nontrivial step is to consider points at the boundary of the disks.

The functions $\exp$, $\sin$, $\cos$ have addition formulas, and the function $\arctan$ satisfies $\arctan(1/x)=(-1)\sp{\mathrm{sign}(x)}(\pi/2)-\arctan x$, for $x\neq 0$, and $\log ax =\log a+\log x$. These formulas allow us to extend their definitions beyond the boundary points of their restrictions.

The functions $\tilde{J}\sp{(j)}$, $j=0,1,2$, admit the transformation fromulas indicated above (the points $q_1$, $q_2$ and $q_3$, as functions of $q$) in order to extend their definitions beyond the boundary points of their restrictions.

This finishes the proof.\hspace*{\fill}$\square$

\medskip

Now we include of the full exponential and restricted trigonometric functions.

\begin{theorem}\label{model-completeness-J-exp}
Let  $\mathcal{R}_J=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<$, $(J\sp{(k)}_{\mathit{re}},J\sp{(k)}_{\mathit{im}})_{0\leq k\leq 2}$, $\mathrm{sin}\lceil_{[-\pi,\pi]}$, $\mathrm{cos}\lceil_{[-\pi,\pi]}$, $\exp\rangle$, where for each $k=0,1,2$,
$$
J\sp{(k)}_{\mathit{re}}(x,y)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(J\sp{(k)}(x+iy)) & \mathrm{if} & |x|\leq\frac{1}{2},\,y\geq\frac{\sqrt{3}}{2};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
J\sp{(k)}_{\mathit{im}}(x,y)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(J\sp{(k)}(x+iy)) & \mathrm{if} & |x|\leq\frac{1}{2},\,y\geq\frac{\sqrt{3}}{2};\\
0 &  & \mathrm{otherwise},
\end{array}\right.
$$
and $J\sp{(k)}(x+iy)$ is the $k\sp{th}$ derivative of the (complex) function $J$ with respect to $z$, with $J\sp{(0)}=J$.
The theory of $\mathcal{R}_J$ is strongly model complete.
\end{theorem}

\textbf{Proof:} We interpret the symbols of $\mathcal{R}_{J_2}$ in $\mathcal{R}_{J}$ by strong existential formulas and use the strong model completeness of $\mathcal{R}_{J_2}$.

The change of variables $q=\exp(2\pi i\tau)$, with inverse $\tau=(\log q)/2\pi i$ are strongly definable from each other. The branch of the logarithm function is strongly definable from $\log$ and from $\arctan$, which is itself strongly definable from the restricted sine and cossine.

From these remarks we conclude that the function symbols of the structure $\mathcal{R}_{J_2}$ are strongly definable in $\mathcal{R}_{J}$.

Now, any formula in the language of $\mathcal{R}_J$ can be translated into a formula in the language of $\mathcal{R}_{J_2}$. The strong model completeness of the latter structure implies that such formula is equivalent with a strong existential formula (and this can be done inside $\mathcal{R}_{J}$).  Therefore $\mathcal{R}_J$ is strongly model complete.\hspace*{\fill}$\square$

\subsection{Quasi-modular Forms}

The definitions and claims about modular and quasimodular forms in this section can be found in \cite{zagier2008}.

A \textbf{modular form of (integer) weight} $k>0$ is a holomorphic function $f:\mathbb{H}\to\mathbb{C}$ such that
$$
f\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)\sp{k}f(\tau)
$$
and of subexponential growth as $\tau\to\infty$ (this implies that $f$ is also holomorphic at $\infty$). We notice that $f(\tau+1)=f(\tau)$, so $f$ admits a \textit{Fourier development}
$\sum_{n\geq 0}a_n\exp(2\pi in\tau)$ (the analycity at $\infty$ implies that the index $n$ varies in the set of nonnegative integers $\mathbb{N}$). It can be shown that these conditions imply that $k\geq 4$.

There are two canonical modular forms of degrees 4 and 6 which generate all the other modular forms:
$$
E_k(\tau)=\frac{1}{2\zeta(k)}\sum_{(m,n)\in\mathbb{Z}\sp{2}\setminus\{(0,0)\}}\frac{1}{(c\tau+d)\sp{k}},
$$
which, for $k>2$, converges absolutely and uniformly in each compact set in $\mathbb{H}$, and $\zeta(k)=\sum_{r\geq 1}(1/r\sp{k})$. The forms
of even integer weight are polynomials in $E_4$ and $E_6$ with complex coefficients.

For $k=2$ the series does not converge absolutely but we can define
$$
G_2(\tau)=\zeta(2)E_2(\tau)=\frac{1}{2}\sum_{n\neq 0}\frac{1}{n\sp{2}}+\frac{1}{2}\sum_{m\neq 0}\sum_{n\in\mathbb{Z}}\frac{1}{(m\tau+n)\sp{2}},
$$
where the sums cannot be interchanged. This defines a \textbf{quasimodular form of weight 2}, which has the transformation formula
$$
G_2\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)\sp{2}G_2(\tau)-\pi ic(c\tau+d),
$$
which is not a modular form. Its importance is that the ring $\mathbb{C}[E_2,E_4,E_6]$ contains all the modular forms and is closed under differentiation because of Ramanujan's formulas
$$
E_2'=\frac{E_2\sp{2}-E_4}{12},\ E_4'=\frac{E_2E_4-E_6}{3},\ E_6'=\frac{E_2E_6-E_4\sp{2}}{2},
$$
where $E'_k(\tau)$ denotes $(1/2\pi i)dE_k/d\tau$.

For the representation of these forms in the variable $q$ (Eisenstein series, which can be viewed as Fourier transforms), $\tilde{E}_k(q)$, this derivative corresponds to $qd\tilde{E}/dq$ and so, the ring $\mathbb{C}[q,\tilde{E}_2,\tilde{E}_4,\tilde{E}_6]$ contains the Fourier transforms of all the modular forms and is closed under differentiation:
$$
q\frac{d\tilde{E}_2}{dq}=\frac{\tilde{E}_2\sp{2}-\tilde{E}_4}{12},\ \ q\frac{d\tilde{E}_4}{dq}=\frac{\tilde{E}_2\tilde{E}_4-\tilde{E}_6}{3},\ \ q\frac{d\tilde{E}_6}{dq}=\frac{\tilde{E}_2\tilde{E}_6-\tilde{E}_4\sp{2}}{2}.
$$

As we have done in the case of the modular function $J$ in the last section, we prove here an auxiliary strong model completeness result for the  forms $\tilde{E}_k$ (defined in some disk around the origin) and then, with the help of the exponential function we prove the strong model completeness for the forms $E_k$.

\begin{theorem}
The following expansions of the field of the real numbers are strongly model complete, where $q=(u+iv)$ and $|q|=\sqrt{x\sp{2}+y\sp{2}}$:
\begin{enumerate}
\item
$\mathcal{R}_{M_1}=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<,(F_{k,n})_{n\in\mathbb{N}},(G_{k,n})_{n\in\mathbb{N}, k=2,4,6}\rangle$, where  for each $n\in\mathbb{N}$ and each $k=2,4,6$,
$$
F_{k,n}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(\tilde{E}_k(q)) & \mathrm{if} & |q|\leq 1-\frac{1}{n+1};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
G_{k,n}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(\tilde{E}_k(q)) & \mathrm{if} & |q|\leq 1-\frac{1}{n+1};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
\item
$\mathcal{R}_{M_2}=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<$, $\mathrm{exp}\lceil_{[0,1]}$, $\mathrm{log}\lceil_{[1,2]}$, $\mathrm{sin}\lceil_{[-\pi,\pi]}$, $\mathrm{cos}\lceil_{[-\pi,\pi]}$, $\arctan\lceil_{[-1,1]}$, $(\tilde{E}_{\mathit{k,re}},\tilde{E}_{\mathit{k,im}})_{k=2,4,6}\rangle$, where for each $k=2,4,6$,
$$
\tilde{E}_{\mathit{k,re}}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(\tilde{E}_k(q)) & \mathrm{if} & |q|\leq 1-\delta;\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
\tilde{E}_{\mathit{k,im}}(q)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(\tilde{E}_k(q)) & \mathrm{if} & |q|\leq 1-\delta;\\
0 &  & \mathrm{otherwise},
\end{array}\right.
$$
where $\delta=\exp(-\pi\sqrt{3})$ and $f\lceil_{[a,b]}$ means the function $f$ restricted to the interval $[a,b]$ and defined as zero elsewhere, for $f$ being the sine cossine exponential and arctangent functions.
\end{enumerate}
\end{theorem}

\textbf{Proof:} It is similar to the proof of Theorem \ref{model-completeness-J} and left to the reader.\hspace*{\fill}$\square$

\medskip

Now we introduce the full exponential function.

\begin{theorem}
We define $\mathcal{R}_M=\langle\mathbb{R},\mathit{constants},+,-,\cdot,<$, $(E_{\mathit{k,re}}, E_{\mathit{k,im}})_{k=2,4,6}$, $\exp$, $\mathrm{sin}\lceil_{[-\pi,\pi]}$, $\mathrm{cos}\lceil_{[-\pi,\pi]}\rangle$, where for each $k=2,4,6$,
$$
E_{\mathit{k,re}}(x,y)=\left\{
\begin{array}{lcl}
\mathfrak{Re}(E_k(x+iy)) & \mathrm{if} & |\mathfrak{Re}(x)|\leq\frac{1}{2},\,y\geq\frac{\sqrt{3}}{2};\\
0 &  & \mathrm{otherwise}.
\end{array}\right.
$$
$$
E_{\mathit{k,im}}(x,y)=\left\{
\begin{array}{lcl}
\mathfrak{Im}(E_k(x+iy)) & \mathrm{if} & |\mathfrak{Re}(x)|\leq\frac{1}{2},\,y\geq\frac{\sqrt{3}}{2};\\
0 &  & \mathrm{otherwise},
\end{array}\right.
$$
The theory of $\mathcal{R}_M$ is strongly model complete.
\end{theorem}

\textbf{Proof:}
It is similar to the proof of Theorem \ref{model-completeness-J-exp} and is left to the reader.\hspace*{\fill}$\square$

\medskip

Entensions and improvements of the results above are commented in the next section.

\section{Concluding remarks}

All the results in this work rely on the (topological) compactness of the real interval $[-1,1]$ (and of the closed polydisks) which introduces a highly uneffective feature in the proofs.

Recently, Angus Macintyre has shown in \cite{macintyre2003} how to prove an effective version of the model completeness of the expansion of the field of the real numbers by the $\wp$ function with parameter $\tau=i$. His proof can be modified to the cases where $\wp$ admits complex multiplication and perhaps to all cases.
The insight of his work is to deal with the inverse function of $\wp$, which is an elliptic integral and thus it is a Pfaffian function (see details in \cite{macintyre2008}), so it is amenable to the treatment used in his work with Alex Wilkie, \cite{macintyre-wilkie1996}.

On the other hand, his methods do not seem to apply to the modular function $J$ and the modular forms $E_4$ and $E_6$ which are not Pfaffian functions (but are \textit{noetherian} functions) and satisfy nonlinear differential equations involving $E_2$, $E_4$ and $E_6$ in a nontriangularisable way. (P. F. Stiller presents in \cite{stiller1988} second order linear equations satisfied by $E_4\sp{1/4}$ and $E_6\sp{1/6}$ which do no mix the two functions, each reducible to a system of two linear first order equations but, as far as we know, not reducible to the Pfaffian functions type.)

\medskip

These remarks suggest the following \textbf{open problems} related to our work:

\begin{enumerate}
\item
Find proofs of effective model completeness for the expansions of the field of the real numbers by modular functions, forms and elliptic functions (as two variable functions). These proofs would be a big step in the direction of the probable proof of the decidability of their theories.
\item
Find a proof of effective model completeness of expansions by (restricted) noetherian functions (those functions which generate a noetherian differential field over $\mathbb{C}$). The differential algebraic methods of \cite{macintyre-wilkie1996} do not immediately apply here, because they rely on the induction on the length of the \textit{Pfaffian chain} defining the functions and also on effective bounds on the number of connected components of the zero sets of systems of equations with Pfaffian functions. See \cite{khovanskii-gabrielov1998,gabrielov-vorobjov2004} for some work on the complexity of Noetherian Systems.
\item
A useful result needed in the methods of \cite{macintyre-wilkie1996} is an effective bound on the number of connected components of the zero sets of a system of Pfaffian functions. Since the full sine function is a noetherian function, we see the need to restrict their domains to compact (poly)intervals. The measure of the complexity of the noetherian functions have to take into account the size of the polyintervals to which they are restricted.
\item
Prove the same type of results now on the context of $p$-adic numbers. A first step was done by Nathana\"el Mariaule in his 2013 PhD Thesis (supervised by Alex Wilkie), \textit{On the Decidability of the $p$-adic Exponential Ring}, \cite{mariaule2013}, where he proves the effective model completeness of $\mathbb{Z}_p$ expanded by $\exp$ and uses the $p$-adic Schanuel Conjecture to prove the relative decidability of its theory.
\item
The results in \cite{macintyre-wilkie1996}, \cite{macintyre2003,macintyre2008} and \cite{mariaule2013} are relative to the truth some very difficult transcendental theoretic conjectures (Schanuel Conjecture and its modular version). Maybe by a finer analysis of the functions defined by terms on those structures we could find estimates which would circumvent the use of those conjectures.
\item
A question directly related with this work is wether the (full) exponential function is necessary to prove the model completeness of those structures. We believe that, for instance, the full exponential function is not existentially definable from the $\wp$ functions (although it is definable, see \cite[Theorem 5.7, p. 545] {peterzil-starchenko-wp2004}).
\end{enumerate}

config: arxiv


text:
\begin{document}
\title{\bf On the non-existence of some Steiner $t$-$(v,k)$ trades of
certain volumes}
\author{
{\sc Mehri Asgari AND Nasrin Soltankhah} \footnote{Corresponding
author: E-mail: soltan@alzahra.ac.ir.}
 \\[5mm]
Department of Mathematics\\ Alzahra University  \\
Vanak Square 19834 \ Tehran, I.R. Iran }

\maketitle
\begin{abstract}
Mahmoodian and Soltankhah $\cite{MMS}$ conjectured that there does
not exist any $t$-$(v,k)$ trade of volume $s_{i}< s <s_{i+1}$,
where $s_{i}=2^{t+1}-2^{t-i},\  i=0,1,\ldots ,t-1$. Also they
showed that the conjecture is true for $i=0$. In this paper we
prove the correctness of this conjecture for Steiner trades.
 \end{abstract}

\hspace*{-2.7mm} {\bf KEYWORDS:} {  \sf trade, Steiner trade,
volume }

\section{Introduction}
\setcounter{preproposition}{0} \setcounter{precorollary}{0}
\setcounter{prelemma}{0} \setcounter{preexample}{0} Let $0<t<k<v $
be three natural numbers and let $X$ be a $v$-set. For every $i,\
0\leq i\leq v $, the set of all $i$-subsets of $X$  will be
denoted by $P_i(X)$, and also for any $i>1 $, we will denote the
set $\{x_1,x_2,\ldots,x_i\} $ by $x_1x_2\ldots x_i$. The elements
of $P_k(X)$ are called \textbf{blocks}. A $t$-$(v,k)$
\textbf{trade}
 $T=\{T_1,T_2\}$ consists of two disjoint
collections of blocks, $T_1$ and $T_2$, such that every element
of $P_t(X)$ is contained  in the same number of blocks in $T_1$
and $T_2$. For simplicity, the notation of $t$-trade is commonly
used in this manuscript. Let $T=\{T_1,T_2\}$ be a $t$-trade.
Clearly, $|T_1|=|T_2|$ and $|T_1|$ is called the \textbf{volume}
of the $T$ and is denoted by \rm {vol(T)} and sometimes we denote
vol(T) by \rm {s}, if it causes no confusion. The subset of $X$
which is covered by $T_1$ and $T_2$ is called the
\textbf{foundation} of T and is denoted by \rm {found(T)}.
Repeated blocks in $T_1(T_2)$ are allowed.

Trade with no repeated block is simple. A $t$-trade is called
\textbf{Steiner} $t$-$(v,k)$ \textbf{trade} if every element of
$P_t(X)$ appears in at most one block of $T_1(T_2)$. It has been
shown in $\cite{{ graham},{HL}}$ that in every $t$-$(v,k)$ trade,
$|$found$(T)|\geq k+t+1$, vol$(T)\geq2^t$. A $t$-trade $T$ with
vol$(T)=2^t$ and $|$found$(T)|= k+t+1$ is called
\textbf{minimal}. A minimal $t$-$(v,k)$ trade is unique, up to
isomorphism, and can be cast in the following form
$T=(x_1-x_2)(x_3-x_4)\ldots(x_{2t+1} - x_{2t+2})x_{2t+3} \ldots
x_{k+t+1}$, where $x_i \in $ found$(T)$. After a formal
multiplication, the terms with plus (minus) signs are to be
considered as block of $T_1(T_2)$. Let $T=\{T_1,T_2\}$ be a
$t$-$(v,k)$ trade of vol$(T)=s$ and $x,y\in$ found$(T)$. Then the
number of blocks in $T_1(T_2)$ which contains $x$ is denoted by
$r_x$, and the number of blocks containing $\{x,y\}$ (for
$t\geq2)$  is denoted by $\lambda_{xy}$. The set of blocks in
$T_1(T_2)$ which contains $x \in$ found$(T)$ is denoted by
$T_{1x}(T_{2x})$ and the set of remaining blocks by
$T^\prime_{1x}(T^\prime_{2x})$. It has been shown $\cite{HL}$ that
if $r_x < s$, then $T_x=\{T_{1x},T_{2x}\}$, is a $(t-1)$-$(v,k)$
trade of vol$(T_x)=r_x$, and furthermore,
$T^\prime_x=\{T^\prime_{1x},T^\prime_{2x}\}$ is a
$(t-1)$-$(v-1,k)$ trade of vol$(T^\prime_x)=s-r_x$. If we remove
$x$ from the blocks of $T_x$ then the result will be a
$(t-1)$-$(v-1,k-1)$ trade which is called a derived trade of $T$
and is denoted by $D_x T=\{(D_x T)_1, (D_x T)_2\}$. It is easy to
show that if T is a Steiner trade, then its derived trade is also
a Steiner trade. If $T=\{T_1,T_2\}$ and $T^*=\{T^*_1,T^*_2\}$ are
two $t$-$(v,k)$ trades, then we define $T+T^*=\{T_1\bigcup
T^*_1,T_2\bigcup T^*_2 \}$ and $T-T^*=\{T_1\bigcup
T^*_2,T^*_1\bigcup T_2\}$. Note that the blocks that appear in
both sides are omitted. It is easy to see that $T \pm T^*$ are
also $t$-$(v,k)$ trades. Let $T$  be a $t$-$(v,k)$ trade and $T
\neq T_x +T_y $ (for $x,y \in$ found$(T))$ then $T-(T_x+T_y)$ is a
$(t-1)$-$(v,k)$ trade with volume $s-(r_x+r_y)+2\lambda_{xy}$
$\cite{HL}$. Hwang $\cite{HL}$ has shown that there is no
$2$-$(v,k)$ trade of volume $s=5$, and as a generalization, she
has also shown that $t$-trades with $s=2^t+1$ do not exist,
Mahmoodian and Soltankhah $\cite{MMS}$ have shown that:

 \begin{theo}~{\rm \cite{MMS}}. There does not exist any $t$-$(v,k)$ trade of volume $s$ such that $2^t<s<2^t + 2^{t-1}$.
\end{theo}

 Also in \cite{MMS}, the
following conjecture has been stated:

 \begin{conjecture}~{\rm \cite{MMS}}.
  There does not exist any $t$-$(v,k)$ trade of {\rm volume} $s$ such that
$2^{t+1} - 2^{t-i}<s<2^{t+1} - 2^{t-i-1},\ \ i=0,1,\ldots,t-1$.
\end{conjecture}

In fact Theorem A is the answer for the conjecture for $i=0$.
Gray and Ramsay $\cite{Gray}$, showed that no $3$-$(v,4)$ trade of
$s=13$ exists, and they also proved a generalization of this: For
$t\geq 3$, $t$-$(v,t+1)$ trades of volume $s=2^t+ 2^{t-1}+1$  do
not exist. Of course this is a partial solution for $i=1$ of the
conjecture. Prior to this proof, in $\cite{hart}$ it is shown
that there does not exist any Steiner $3$-$(v,4)$ trade of $s=13$.
Hoorfar and G.B. Khosrovshahi $\cite{khosro}$ established the
correctness of this conjecture for Steiner trades, for $i=1$.
 In this paper, we prove the correctness of the conjecture for Steiner
 trades,   for $i=0,\cdots,t-1$. In other words we show that the
 conjecture is true for Steiner trades .

\section{Some necessary results }
\setcounter{theorem}{0} \setcounter{preproposition}{0}
\setcounter{precorollary}{0} \setcounter{prelemma}{0}
\setcounter{preexample}{0}

The  following results are  useful in our discussion.

\begin{lemma}~{\rm \cite{khosro}}.
\label{l1} In every Steiner $t$-trade $T=\{T_1,T_2\}$ with  $k =
t+1$, volume $s$ and for every $x\in $found$(T)$, we have $r_x\leq
\frac{1}{2} s$.

\end{lemma}

\begin{theorem}~{\rm \cite{khosro}}.\label{c2}
Let $T=\{T_1,T_2\}$ be a Steiner $t$-$(v,k)$ trade with $k> t+1$
and of volume $s$, then $ s \geq (t-1)2^t +2$.

\end{theorem}

\section{Main result}
In this section we investigate the main theorem in two cases:
$k=t+1$ and $k>t+1$. Note that as a result of Theorem~\ref{c2} ,
it follows that for $t=2$, we have $s\geq6$ and for $t>2$, we
have $s\geq 2^{t+1}+2$. Therefore Theorem~\ref{c2} establishes
the truth of the Conjecture for any Steiner trade with $k> t+1$.
Therefore the case $k=t+1$ remains to prove, which we discuss it
in the following Theorem.

\begin{theorem}.
 For $t\geq 3$, there does not exist any Steiner
$t$-$(v,t+1)$ trade of volume $s$ such that
$2^{t+1}-2^{t-i}<s<2^{t+1}-2^{t-i-1},\  i=0,1,\ldots t-1 $.

\end{theorem}

\begin{proof}
{Induction on $i$. For $i=0$, this is true by Theorem A. Suppose
that the theorem is correct for values smaller than
$i\ (i>1)$ and we have to establish it for $i$.\\
 Now induction on $t$.\\
 The minimum possible value on t is equal to $i+2$.
First we show, the nonexistence of these $t$-trades.\\
 If $t=i+2$, then $s=2^{t+1}-3$.
Suppose that the statement is not correct and there exists a
Steiner $t$-$(v,t+1)$ trade $T$ of volume $s=2^{t+1}-3$ and
$|$found$(T)|=f$. Then we derive a contradiction.\\
 Consider $x\in$ found$(T)$, since $D_x T $ is a Steiner $(t-1)$-trade
with $k=t$ and volume $s=r_x$, therefore $r_x\geq 2^{t-1} $. On
the other hand by Lemma 2.1, we
have $r_x\leq \frac{s}{2}$.\\
$ \Rightarrow r_x\leq \frac{s}{2}=\frac{2^{t+1}-3}{2}\leq 2^t -
2$.\\
 Therefore $2^{t-1}\leq r_x \leq 2^t-2$.  But by induction assumption,
only values remain to be checked are: $r_x =2^t -2^{t-u}\
(u=1,\ldots ,i+1)$.
\vspace{.2cm}\\
 \textbf{{Case A.1:}}  there exists $x\in$ found$(T)$ such
that $r_x=2^{t-1}$ then,\\
 \textbf{\textrm(a)} suppose that there
exists $y\in$ found$(T)$ such that $\lambda_{xy}=0 $. this
\textsl{leads} to a contradiction. To see this we look at $T-(T_x
+T_y)$ which is a $(t-1)$-$(v,k')$ trade of volume $
s^\prime=s-(r_x+r_y)
=2^{t+1}-3-2^{t-1}-r_y.$\\
$\Rightarrow 2^t+2^{t-1}-3-2^t+2\leq s^\prime
\leq 2^t+2^{t-1}-3-2^{t-1}$;\\
$\Rightarrow 2^{t-1}-1\leq s^\prime \leq 2^t-3$.\\
 If $k' >t $, by Theorem 2.1 is
impossible.
 If $k'=t$ since $s^\prime $ is odd and by induction assumption,
 $s\prime $ can not take a possible value.\\
 \textbf{\textrm{(b)}} suppose that for every $y\in$ found$(T)$, $y\neq
x$
 , we have $\lambda_{xy}\neq 0$ then $|$found$(T_x)|=|$found$(T)|=f$.
  Now, since $T_x$ is a $(t-1)$-trade with $k=t+1$ and volume
$r_x=2^{t-1}$ such that $x$ appears in all its blocks. Must be of
the form
\begin{center}
$T_x=(y_1-y_2)\ldots (y_{2t-1}-y_{2t})x.$
\end{center}
 We note that $f=2t+1$. This is a contradiction since in
$T$ we have
\begin{center}
$ f \geq  k+t+1=2t+2$.
\end{center}
\textbf{{Case A.2:}} for every $x\in$ found$(T):\  r_x\geq
2^t-2^{t-2}.
$\\
\textbf{\textrm{(a)}} again suppose that there exists $y\in$
found$(T);$ \ $y\neq x $ such that  $\lambda_{xy}=0. $ Then the
volume $s^\prime$ of the $(t-1)$-trade $T-(T_x+T_y)$ is:
$s^\prime=s-(r_x+r_y)=2^{t+1}-3-(r_x+r_y)$. With considering the
values $r_x$ and $r_y$ we have
\begin{center}
$1\leq s^\prime\leq 2^{t-1}-3$ \\
\end{center}
since minimum volume from $(t-1)$-trade is $2^{t-1}$ it is a contradiction.\\
 \textbf{\textrm{(b)}} now for every $x,y \in$ found$(T)$ we have
 $\lambda_{xy}
 \neq0 .$\\
 Therefore:\\
 if $ r_x=2^t-2^{t-u}, \hspace{2 cm}u=2,\ldots ,i+1 $;\\
       $\lambda_{xy}=2^{t-1}-2^{t-l},\hspace{2 cm}  l=2,\ldots, u+1.
$\\
\textbf{i:} $\exists y\in$ found$(T),\ \lambda_{xy} =
2^{t-1}-2^{t-l},\hspace{1 cm} l=2,\ldots, u$.\\
In this case volume $(t-1)$-trade $T-(T_x+T_y)$ is:
$s^\prime=s-(r_x+r_y)+2\lambda_{xy}$
\begin{center}
$\Rightarrow 2^{t-1}+1\leq s^\prime \leq 2^t-3$.
\end{center}
 Since $s^\prime $ is odd and by induction assumption,
 $s^\prime$ can not take a possible value.\\
\textbf{ii:} $\forall y\in$ found$(T),\
\lambda_{xy}=2^{t-1}-2^{t-u-1}$.\\
 In this case to reach a contradiction, counting
the pairs $(y,B); y\in B\in (D_xT) $ in two ways we obtain
$$
 \sum_{y\in {\rm found}(D_xT)}\lambda_{xy}=t.{\rm vol}(D_xT).$$

Since $|$found$(D_xT)|=f-1$, therefore
\begin{center}
$(f-1)(2^{t-1}-2^{t-u-1})=t(2^{t}+2^{t-u})$ \\
$\Rightarrow f=2t+1,$
\end{center}
and this is in contradiction with $ f\geq k+t+1=2t+2$.\\

Now suppose by induction assumption that the theorem is correct
for values smaller than $t(t>i+2)$ and we show it for $t$. Suppose
that the statement is not correct and there exists a Steiner
$t$-$(v,t+1)$ trade T of volume $s=2^t+2^{t-1}+\cdots +2^{t-i}+j$
where $ 0<j<2^{t-1-i}.
$ Then we derive a contradiction.\\

Consider $x\in$ found$(T)$. Since $D_xT$ is a Steiner
$(t-1)$-trade with $k=t$ and volume $s=r_x$, therefore $r_x\geq
2^{t-1}$ and on  the other hand we have $r_x\leq \frac{s}{2}$.
Now by induction
assumption:\\
$r_x=2^t-2^{t-u}$ where $u=1,2,\ldots,i+1. $
\vspace{.2cm}\\
 \textbf{{Case B.1:} } there exists $x\in$ found$(T)$ such
that $r_x=2^{t-1}$ then\\
 \textbf{\textrm(a)} suppose that there
exists $y\in$ found$(T)$ such that $\lambda_{xy}=0$. For
$(t-1)$-trade $T-(T_x+T_y)$
\begin{center}
$s^\prime
=s-(r_x+r_y)=2^{t+1}-2^{t-i}+j-(2^{t-1}+2^t-2^{t-u})=2^{t-1}+2^{t-u}-2^{t-i}+j.$
\end{center}

$\begin{array}{l} {\rm if}\hspace{1 cm}u=1 \hspace{3
cm}s^\prime=2^t-2^{t-i}+j
 \hspace{3 cm} 0<j<2^{t-i-1}\\
\end{array}$\\
$\begin{array}{l} {\rm if}\hspace{0.5 cm}2\leq u\leq i
\hspace{2cm}$
$2^{t-1}<s^\prime<2^{t-1}+2^{t-2}\\
\end{array}$\\
$\begin{array}{l}
 {\rm if}\hspace{1 cm} u=i+1 \hspace{2.5 cm}
s^\prime=2^{t-1}-2^{t-i-1}+j<2^{t-1}-2^{t-i-1}+2^{t-i-1}<2^{t-1}.
\end{array}$\\
In the first case according to induction assumption  for $(i-1)$,
there does not exist any $(t-1)$-trade of this volume.
\vspace{.2cm}\\
 In the second case  according to induction assumption
 for $i=0$ there does not exist any  $(t-1)$-trade of
this volume.
\vspace{.25cm}\\
 And ultimately the last case is in contradiction
with minimum volume from $(t-1)$-trade.
\vspace{.2 cm}\\
 \textbf{\textrm(b)} suppose that for every $y\in$ found$(T)$, $y\neq x$
 we have $\lambda_{xy}\neq 0.$\\
 The
non-existence of T can be proved the same way as in the case
$t=i+2.$
 \vspace{.2cm}\\
 \textbf{{Case B.2:}} for every $x\in$ found$(T)\  r_x\geq 2^t-2^{t-2}. $\\
 \textbf{\textrm{(a)}}
 Again suppose that there exists $y\in$ found$(T) ;\ y\neq x $
 such that $\lambda_{xy}=0. $\\
 For $(t-1)$-trade $T-(T_x+T_y)$\\
$ s^\prime
=s-(r_x+r_y)=2^{t+1}-2^{t-i}+j-(2^t-2^{t-u}+2^t-2^{t-u^\prime})
\hspace{0.2 cm}$
where $u,u^\prime \geq2$\\
$\Rightarrow s^\prime =2^{t-u}+2^{t-u^\prime}-2^{t-i}+j\leq
2^{t-2}+2^{t-2}-2^{t-i}+j \leq 2^{t-1}-2^{t-i}+j$\\
by assumption $0<j<2^{t-i-1}$ we have $s\prime <2^{t-1}$ which
this is in contradiction with minimum volume from $(t-1)$-trade.\\
 \textbf{\textrm{(b)}} now for every $x,y \in$ found$(T),\ r_x\leq r_y $
we have
 $\lambda_{xy}
 \neq0 .$\\
 if $ r_x=2^t-2^{t-u},$ \hspace{1 cm}  $  u=2,\ldots ,i+1 $\\
      $\lambda_{xy}=2^{t-1}-2^{t-l}, \hspace{0.5 cm} l=2,\ldots, u+1$
\\
       $r_y=2^{t}-2^{t-u^\prime}, \hspace{1 cm} u^\prime=u,\ldots
,i+1$.\\
 \textbf{i:} $\exists y\in$ found$(T),$ \ $\lambda_{xy} =
2^{t-1}-2^{t-l}, \ l=2,\ldots, u$.\\
  In this case for $(t-1)$-trade $T-(T_x+T_y)$ have:
\begin{center}
$s^\prime=2^t+2^{t-u}+2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j$\\
where  $u=2,\ldots ,i+1$;\\
\hspace{1cm} $l=2,\ldots ,u$;\\
\hspace{2.5cm} $u^\prime=u, \ldots, i+1$.\\
\end{center}
 Therefore $l\leq u\leq u^\prime $
 {we have four cases}:
 \vspace{.22 cm}\\
 \textbf{1)} $u=u^\prime=l$ \hspace{1 cm} $\Rightarrow s^\prime
 =2^t-2^{t-i}+j$.
\vspace{.22 cm}\\
 $(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t+2^{t-u}+
2^{t-u}-2^{t-i}-2^{t-u+1}+j=2^t-2^{t-i}+j)$
\vspace{.1 cm}\\
\textbf{2)} $u=l<u^\prime\leq i$  \hspace{1 cm} $\Rightarrow
2^t-2^{t-l}<s^\prime<2^t-2^{t-l-1}$.
\vspace{.22 cm}\\
 $(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t+2^{t-l}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l}+\underbrace{(2^{t-u^\prime}-2^{t-i})}_{\geq0}+\underbrace{j}_{>0}>2^t-2^{t-l})$
\vspace{.15 cm}\\
 $(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t+2^{t-l}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l}+2^{t-u^\prime}-2^{t-i}+j=2^t-2^{t-l-1}-2^{t-l-1}
+2^{t-u^\prime}-2^{t-i}+j=2^t-2^{t-l-1}+\underbrace{(2^{t-u^\prime}-2^{t-l-1})}_{\leq0}+\underbrace{(j-2^{t-i})}_{<0}<2^t-2^{t-l-1})$
\vspace{.22 cm}\\
 \textbf{3)} $u=l<u^\prime=i+1$  \hspace{1 cm} $\Rightarrow
2^t-2^{t-l+1}<s^\prime<2^t-2^{t-l}$.
\vspace{.22 cm}\\
 $(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t+2^{t-l}+
2^{t-i-1}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l+1}+
\underbrace{(2^{t-l}-2^{t-i-1})}_{>0}+\underbrace{j}_{>0}>2^t-2^{t-l+1})$
\vspace{.15 cm}\\
$(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t+2^{t-l}+
2^{t-i-1}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l}+2^{t-i-1}+j=2^t-2^{t-l}+\underbrace{(j-2^{t-i-1})}_{<0}
<2^t-2^{t-l})$
\vspace{.22 cm}\\
 \textbf{4)} $l<u\leq
u^\prime$\hspace{1 cm} $\Rightarrow
2^t-2^{t-l+1}<s^\prime<2^t-2^{t-l}$.
\vspace{.22 cm}\\
$(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j\geq2^t+2^{t-i-1}+
2^{t-i-1}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l+1}+\underbrace{j}_{>0}>2^t-2^{t-l+1})$
\vspace{.15 cm}\\
 $(s^\prime=2^t+2^{t-u}+
2^{t-u^\prime}-2^{t-i}-2^{t-l+1}+j=2^t-2^{t-l}-
2^{t-l}+2^{t-u}+2^{t-u^\prime}-2^{t-i}+j\leq2^t-2^{t-l}-
2^{t-l}+2^{t-u}+2^{t-u}-2^{t-i}+j=2^t-2^{t-l}-2^{t-l}+2^{t-u+1}-2^{t-i}+j=
2^t-2^{t-l}+\underbrace{(2^{t-u+1}-2^{t-l})}_{\leq0}+\underbrace{(j-2^{t-i})}_{<0}<2^t-2^{t-l})$\\

All of the above cases are in contradiction with induction
assumption.\\
\textbf{ii:} $\forall y\in$ found$(T)$,  $ \
\lambda_{xy}=2^{t-1}-2^{t-u-1}$.\\
 In this case the non-existence of T can be proved the same way as in
the case $t=i+2$ (Case A.2(b)ii). }

\end{proof}
\vspace{.2cm} \textbf{Remark:} In this sequel we improved the
conjecture for Steiner trade. It remained for interested reader
to prove the correctness of this conjecture for any trade.

\vspace{.2cm}\\
 \textbf{Acknowledgement:} The authors thank the
referees who helped us to improve  presentation of this
manuscript.


text:
\begin{document}

\maketitle

\begin{abstract}
Let $M$ be a matroid on ground set $E$. A subset $l\subseteq E$ is called a \emph{line} when $r(l)\in \{1,2\}$. Given a set of lines $L=\{l_1,\ldots, l_k\}$ in $M$, a vector $x\in \Rplus^L$ is called a \emph{fractional matching} when $\sum_{l\in L} x_l a(F)_l\leq r(F)$ for every flat $F$ of $M$. Here $a(F)_l$ is equal to $0$ when $l\cap F=\emptyset$, equal to $2$ when $l\subseteq F$ and equal to $1$ otherwise. We refer to $\sum_{l\in L}x_l$ as the \emph{size} of $x$.

It was shown by Chang et al. that a maximum size fractional matching can be found in polynomial time. In this paper we give an efficient algorithm to find for given weight function $w:L\to \Q$ a \emph{maximum weight} fractional matching. \newline
\newline
\textbf{Keywords:} matroid, matroid matching, matroid parity, fractional matching, lattice polytope, algorithm.
\end{abstract}

\section{Introduction}
Let $M$ be a matroid on the set $E$, and let $\{a_1,b_1\},\ldots,\{a_k,b_k\}$ be disjoint pairs of elements from $E$. A subset $I$ of $\{1,\ldots,k\}$ is called a \emph{matching} if $\bigcup_{i\in I} \{a_i,b_i\}$ is an independent set in the matroid $M$. The problem of finding a maximum size matching is called the \emph{matroid matching problem} and was proposed by Lawler \cite{Lawler} as a common generalization of non-bipartite matching and matroid intersection.

Lov\'asz \cite{Lovasz} and, independently, Korte and Jensen \cite{KorteJensen} showed that for general matroids given by an independence oracle, the matroid matching problem requires an exponential number of oracle calls, and hence is not solvable in polynomial time. Also, the problem of finding a maximum size clique in a graph can be formulated as a matroid matching problem, where the oracle is removed and independence can be read off from the input graph directly, showing that the matroid matching problem contains NP-hard problems (see \cite{Lex}).

However, matroid matching has become a powerful tool in combinatorial optimization since Lov\'asz \cite{Lovasz} proved a min-max formula and constructed a polynomial time algorithm for matroid matching in representable matroids that are given by an explicit linear representation over a field. Already linear matroid matching has a wide range of applications, among which are a polynomial time algorithm for packing Mader paths \cite{Lex}, graph rigidity \cite{Lovasz2} and computing the maximum genus surface in which an input graph can be embedded \cite{genus}.
More efficient algorithms for linear matroid matching have been developed by Gabow and Stallmann \cite{GabowStallmann} and by Orlin and Vande Vate \cite{OrlinVandeVate}.

An outstanding problem concerning matroid matching is to construct an efficient algorithm for finding a \emph{maximum weight} matching for linearly represented matroids.

To gain better understanding of the matroid matching polytope, Vande Vate \cite{FMM} introduced a fractional relaxation of this polytope, called the \emph{fractional matroid matching polytope}. The integer points of this polytope correspond exactly to the matroid matchings, and although the polytope itself is not integer, the vertices are half-integer. Furthermore, in the two extremes where the matroid matching is in fact a matroid intersection problem or a non-bipartite matching problem, the fractional matroid matching polytope coincides with the common independent set polytope and with the fractional matching polytope respectively.

In a series of two papers, Chang, Llewellyn and Vande Vate \cite{FMM-duality, FMM-algorithm} showed that there exists a polynomial time algorithm to optimize the all-one objective function over the fractional matroid matching polytope.

In the present paper, we consider optimizing arbitrary weight functions over the fractional matroid matching polytope. Extending the result from \cite{FMM}, we show that not only is the polytope half-integer, the system defining the polytope is in fact half-TDI. Our main result is the construction of a polynomial time algorithm for optimizing arbitrary weight functions over the fractional matroid matching polytope, showing that the polytope is algorithmically tractable.

\section{Preliminaries}

Let $M$ be a matroid with groundset $E$ and rankfunction $r_M$. Here we will assume that $M$ does not have loops. The set $E$ need not be finite, but we do require that $M$ has finite rank. The span of $X\subseteq E$ is denoted by $\cl_M (X)$, the smallest flat containing $X$. The set $\mathcal{L}(M)$ of flats of the matroid $M$ form a lattice, with join $S\join T:=\cl_M (S\cup T)$ and meet $S\meet T:=S\cap T$. The rank function $r_M$ is submodular on $\mathcal{L}(M)$:
\begin{equation}r_M(S)+r_M(T)\geq r_M(S\cup T)+r_M(S\cap T)=r_M(S\join T)+r_M(S\meet T)\quad \text{for all $S,T\in \mathcal{L}(M)$.}
\end{equation}
When the matroid is clear from the context, we will suppres the matroid in the notation. For further notation and preliminaries on matroids, we refer the reader to \cite{Oxley}.

Let $L$ be a finite set of \emph{lines} of $M$, where a \emph{line} is a subset of $E$ of rank $1$ or $2$. We do not require the lines to be flats. For any subset $X\subseteq E$, we define its \emph{degree vector} $a(X):L\to \{0,1,2\}$ by
\begin{equation}\label{Degreevector}
a(X)_l:=
\begin{cases}
 0 & \text{if $X\cap l=\emptyset$,}\\
 2 & \text{if $X\supseteq l$,}\\
 1 & \text{otherwise.}
\end{cases}
\end{equation}

It is important to observe that for every line $l\in L$ the function $a(\cdot)_l:\mathcal{L}(M)\to \{0,1,2\}$ is \emph{supermodular}:
\begin{equation}
a(S)_l+a(T)_l\leq a(S\join T)_l+a(S\meet T)_l\quad\text{for all $l\in L$ and all $S,T\in\mathcal{L}(M)$.}
\end{equation}
This follows from simple case-checking. The only nontrivial case is when $a(S)_l=a(T)_l=1$. In that case either $l\cap (S\cap T)\neq \emptyset$ so that $a(S\wedge T),a(S\vee T)\geq 1$ or $l\cap (S\setminus T), l\cap (T\setminus S)\neq \emptyset$ and hence $l\subseteq S\vee T$.

A vector $x\in \R^L$ is called a \emph{fractional matching in $(M,L)$} when
\begin{eqnarray}\label{FMpolytope}
x&\geq &0,\nonumber\\
a(T)\cdot x&\leq&r(T) \text{ for every flat $T$ of $M$}.
\end{eqnarray}
The set of fractional matchings in $(M,L)$ is called the \emph{fractional matching polytope}. Although the number of flats may be infinite, the number of distinct degree-vectors $a(T)$ is finite and hence the fractional matching polytope is indeed a polytope.

We refer to $|x|:=\sum_{l\in L}x_l$ as the \emph{size} of $x$. The maximum size of a fractional matching in $(M,L)$ is denoted by $\nu^*(M,L)$. The size of a fractional matching $x$ is at most $\frac{1}{2}r(E)$, and when equality holds, $x$ is called a \emph{perfect} fractional matching.

In what follows, it will be convenient to work with finite formal sums of flats, that is, expressions of the form $y=\sum_{F\in \mathcal{L}(M)} \lambda_F F$, where $\lambda\in \R^{\mathcal{L}(M)}$ and $\lambda_F=0$ for all but a finite number of flats $F$. We denote $y_F:=\lambda_F$ and $\supp(y):=\{F\mid y_F\not=0\}$. We extend all functions on the $\mathcal{L}(M)$ linearly to finite formal sums and write $r(y):=\sum_F \lambda_F r(F)$ and $a(y):=\sum_F \lambda_F a(F)$.

Consider the program of optimizing a nonnegative weight function $w:L\to\N$ over the fractional matching polytope:

\begin{eqnarray}\label{primal}
\text{maximize}&&w\cdot x\nonumber\\
\text{subject to}&&x\geq 0\nonumber\\
&&a(T)\cdot x\leq r(T)\quad \text{for all $T\in\mathcal{L}(M)$}.
\end{eqnarray}

The dual linear program is given over vectors $y\in\R ^{\mathcal{L}(M)}$ by
\begin{eqnarray}\label{dual}
\text{minimize}&& r(y)\nonumber\\
\text{subject to}&&y\geq 0\nonumber\\
&&a(y)\geq w.
\end{eqnarray}

It was shown in \cite{FMM} that the fractional matching polytope is half-integer and that for $w=\one$, there is a half-integer optimal dual solution. Here we show that the system (\ref{primal}) is half-TDI. That is, for every $w:L\to \N$, the dual has a half-integer optimal dual solution. This implies half-integrality of the fractional matching polytope (see \cite{Linearprogramming}).

\begin{theorem}
System (\ref{primal}), describing the fractional matching polytope, is half-TDI.
\end{theorem}
\begin{proof}
We show that the dual linear program (\ref{dual}) has a half-integer solution. Let $y$ be an optimal solution for which $f(y):=\sum_{F\in \mathcal{L}(M)} y_F r(F)^2$ is maximal. Such a $y$ exists, because we may restrict to a finite number of flats, one representative for each degree-vector, and because the function $f(y)$ is bounded from above by $r(E)\cdot r(y)$.

The support $\mathcal{L}^+:=\supp (y)$ of $y$ is a chain. Indeed, suppose that $S,T\in\mathcal{L}^+$ and $S\not\subseteq T, T\not\subseteq S$. We may assume that $r(T)\geq r(S)$. Let $\epsilon:=\min \{y_S,y_T\}>0$, and define $y':=y+\epsilon(S\meet T+S\join T-S-T)$. Then $y'$ is a feasible solution to (\ref{dual}) by supermodularity of the $a(\cdot)_l$, $l\in L$. By the submodularity of $r$, $y'$ will be an optimal dual solution and $d:=r(S\join T)-r(T)=r(S)-r(S\meet T)>0$. It then follows that $f(y')-f(y)=2\epsilon d\cdot(r(T)-r(S)+d)\geq 2\epsilon d\cdot d>0$, contradicting the choice of $y$.

Denote $\mathcal{L}^+=\{T_1,\ldots, T_k\}$ where $T_1\subset \cdots\subset T_k$. Let $A\in \{0,1,2\}^{\{1,2,\ldots,k\}\times L}$ given by $A_{i,l}:=a(T_i)_l$ be the matrix with the degree vectors of the $T_i$ as rows. To prove that there exists a half-integral optimum $y$, it suffices to show that every non-singular square submatrix $A'$ of $A$ has a half-integer inverse. Since $A'^{-1}=(UA')^{-1}U$, where
$$U=
\begin{pmatrix}
1&0&\cdots&\cdots&0\\
-1&\ddots&\ddots&&\vdots\\
0&\ddots&\ddots&\ddots&\vdots\\
\vdots&\ddots&\ddots&\ddots&0\\
0&\hdots&0&-1&1
\end{pmatrix},$$
it suffices to show that $D:=UA'$ has a half-integer inverse. This follows from the following claim.
\begin{claim}
Let $D\in \{0,1,2\}^{n\times n}$ be a nonsingular matrix with column sums at most $2$, and let $b\in \Z^n$. Then the unique solution $x$ of $Dx=b$ is half-integer.
\end{claim}
\begin{proof}[Proof of claim.]
The proof is by induction on $n$. If some entry $x_i$ of $x$ is integer, then by deleting column $i$ and some row $j$ of $D$, we obtain a nonsingular matrix $D'$, and we can apply induction. Hence we may assume that the coefficients of $x$ are all non-integer. This implies that all column sums of $D$ are equal to $2$. If some entry $D_{i,j}$ of $D$ equals $2$, we can apply induction by deleting row $i$ and column $j$ of $D$. Hence we may assume that all columns of $D$ contain two entries that equal $1$. Thus $D$ is the edge-node incidence matrix of a graph $G=(V,E)$, and $x$ is the unique perfect fractional $b$-matching in $G$. If $d_G(v)=1$ for some $v\in V$, say $vz\in E$, then $x(vz)=b(v)\in \Z$, contradicting our assumption. If all degrees are at least $2$, then since $|V|=|E|$, $G$ is the union of (odd) cycles. The half-integrality of $x$ is then obvious. \end{proof}
\end{proof}

Let $S\subseteq T$ be flats in $M$. The sum $\frac{1}{2}(S+T)$ is called a \emph{cover of $(M,L)$} if $a(S+T)_l\geq 2$ for every line $l\in L$. The cover is called \emph{mimimum} if $r(\frac{1}{2}(S+T))=\nu^*(M,L)$. So the minimum covers are the optimal solutions $y$ with $\supp (y)$ a chain, of the dual program (\ref{dual}) for $w=\one$.

When $\frac{1}{2}(S+T)$ and $\frac{1}{2}(S'+T')$ are two minimum covers, also $\frac{1}{2}(S\meet S'+T\join T')$ is a minimum cover (see \cite{FMM-duality}). It follows that there is a `canonical' minimum cover $\frac{1}{2}(S^*+T^*)$ with the property that $S^*\subseteq S\subseteq T\subseteq T^*$ for every minimum cover $\frac{1}{2}(S+T)$. This cover is called the \emph{dominant cover} in \cite{FMM-duality}, where a characterization of the dominant cover was given in terms of the maximum size fractional matchings. The \emph{closure} of a fractional matching $x$, denoted by $cl(x)$, is defined to be the smallest flat containing the lines in the support of $x$.

\begin{theorem}\label{dominant} \cite{FMM-duality} Let $\frac{1}{2}(S^*+T^*)$ be the dominant cover of $(M,L)$. Then $T^*=\bigcap_x \cl(x)$, where $x$ runs over all  maximum size fractional matchings in $(M,L)$.
\end{theorem}
\begin{theorem}\label{closure} \cite{FMM-duality}
If $x$ is a vertex of the fractional matroid matching polytope, then the closure $cl(x)$ is a tight flat with respect to $x$, i.e.\ $|x|=r(cl(x))$ holds.
\end{theorem}
The characterization of $T^*$ in the Theorem \ref{dominant} implies that
\begin{equation}
S^*=\cl(\bigcup_{l\not\subseteq T^*}(T^*\cap l),
\end{equation}
since $S^*\subseteq T^*$ and $\frac{1}{2}(S^*+T^*)$ must cover each line $l\in L$.

Chang et al. \cite{FMM-algorithm} presented an algorithm that given the matroid $M$ and the set of lines $L$, computes the dominant cover and a maximum size (extreme) fractional matching $x$ in time polynomial in $|L|$ and $r(E)$. More precisely, the matroid $M$ is given by a rank-oracle. To accomodate infinite matroids (of finite rank), and in particular full linear matroids, the groundset $E$ and the lines $L$ are not given explicitly. Rather, it suffices that there is an oracle that takes as input a line $l$ and a flat $F$ represented by a base of $F$, and outputs a base for $l\cap F$.

In this paper, we use this algorithm to construct an algorithm that finds, for given weights on the lines, a maximum weight fractional (perfect) matching and an optimal dual solution.

Our algorithm uses direct sums of minors of the matroid $M$. To make the above oracle available in those matroids, it will suffice that the oracle in addition to a base of $l\cap F$ also provides a base of $l\setminus F$.

\section{A matroid operation}
Given a chain $\mathcal{F}=\{F_1,\dots,F_k\}$ of flats with $F_1\subset F_2\cdots\subset F_k$, we define the matroid $M\contract \mathcal{F}$ on the same ground set $E$ by:
\begin{equation}
M\contract\mathcal{F}:=\bigoplus_{i=0}^k (M|F_{i+1})/F_{i},
\end{equation}
where we set $F_0:=\emptyset$ and $F_{k+1}:=E$.
Observe that when $M$ has no loops (as will always be assumed), also $M\contract \mathcal{F}$ has no loops. The flats of $M\contract \mathcal{F}$ are precisely the sets $S_0\cup\cdots\cup S_k$, with $S_i\subseteq F_{i+1}\setminus F_i$ and $S_i\cup F_i$ is a flat of $M$ for every $i=0,\ldots, k$.

For $X\subseteq E$, we can write $X=X_0\cup\cdots\cup X_k$, where $X_i:=X\cap (F_{i+1}\setminus F_i)$ and we take $F_0:=\emptyset$ and $F_{k+1}:=E$. Using the submodularity of the rank function, we see that
\begin{eqnarray}\label{rankdecreases}
r_{M\contract \mathcal{F}} (X)&=&\sum_{i=0}^k r_{M\contract\mathcal{F}}(X_i)\nonumber\\
&=&\sum_{i=0}^k (r(X_i\cup F_i)-r(F_i))\nonumber\\
&\leq &\sum_{i=0}^k (r(X\cap F_{i+1})-r(X\cap F_i))\nonumber\\
&=&r(X).
\end{eqnarray}

We denote the \emph{closure} of $X\subseteq E$ in the matroid $M\contract \mathcal{F}$ by $X\contract\mathcal{F}$:
\begin{equation}
X\contract\mathcal{F}:=\bigcup_{i=0}^k \left( \cl((X\cap F_{i+1})\cup F_i))\setminus F_i \right) .
\end{equation}

It is useful to observe that when $\mathcal{F}=\mathcal{F}_1\cup\mathcal{F}_2$, the equality $M\contract\mathcal{F}=(M\contract\mathcal{F}_1)\contract\mathcal{F}_2$ holds. In general, for a subset $X\subseteq E$ we only have the inclusion $X\contract\mathcal{F}\subseteq (X\contract\mathcal{F}_1)\contract\mathcal{F}_2$.

Since no loops are created when constructing $M\contract \mathcal{F}$ from $M$ it follows from (\ref{rankdecreases}) that every line in $M$ is a line in $M\contract{F}$ as well. We should stress that the degree vector $a(X)$ of $X\subseteq E$ does not depend on the matroid and is the same for $M$ as for $M\contract \mathcal{F}$.

In the following lemma's we investigate the relations between fractional matchings in the matroids $M$ and $M\contract\mathcal{F}$.

\begin{lemma}\label{contract1}
Let $S=S_0\cup\cdots\cup S_k$ be a flat in $M\contract \mathcal{F}$, whith $S_i\subseteq F_{i+1}\setminus F_i$. Then
\begin{equation}
a(S)=\sum_{i=0}^k \left[a(S_i\cup F_i)-a(F_i)\right].
\end{equation}
\end{lemma}
\begin{proof}
For $i=0,\ldots,k$ let the flat $T_i$ be the flat in $M$ defined by $T_i:=S_i\cup F_i$. Since $a(S)=\sum _i a(S_i)$, we have to show that for every $l\in L$ and $i=0,\ldots,k$ the equality $a(S_i)_l+a(F_i)_l=a(T_i)_l$ holds. Since $S_i$ and $F_i$ are disjoint, the cases where $a(S_i)_l\in \{0,2\}$ or $a(F_i)\in \{0,2\}$ are clear. In the remaining case $l\cap S_i\not=\emptyset$ and $l\cap F_i\not=\emptyset$. Since $F_i$ is a flat in $M$, this implies that $r(l\cap T_i)>1$. This implies $l\subseteq T_i$, since $r(l)\leq 2$ and $T_i$ is a flat in $M$.
\end{proof}

The following proposition shows that a fractional matching in $M\contract{\mathcal{F}}$ is a fractional matching in $M$ as well. Conversely, when we have a fractional matching in $M$, it is also a fractional matching in $M\contract \mathcal{F}$, provided that the flats in $\mathcal{F}$ are tight with respect to the fractional matching.
\begin{proposition}\label{liftx} If $x$ is a fractional matching in $(M\contract \mathcal{F},L)$, then $x$ is a fractional matching in $(M,L)$. If $x$ is a fractional matching in $(M,L)$, and $a(F)x=r_M(F)$ for every $F\in \mathcal{F}$, then $x$ is a fractional matching in $(M\contract\mathcal{F},L)$.
\end{proposition}

\begin{proof}
To prove the first statement, let $T$ be a flat of $M$. Then
\begin{equation}
a(T)x\leq a(T\contract\mathcal{F})x\leq r_{M\contract\mathcal{F}}(T\contract\mathcal{F})\leq r_M(T).
\end{equation}

To prove the second statement, let $S=S_0\cup\cdots\cup S_k$ be a flat in $M\contract \mathcal{F}$. Then
\begin{eqnarray}
a(S)x&=&\sum_{i=0}^k \left[a(S_i\cup F_i)-a(F_i)\right]x\nonumber\\
&=&\sum_{i=0}^k \left[a(S_i\cup F_i)x-r_M(F_i)\right]\nonumber\\
&\leq&\sum_{i=0}^k \left[r_M(S_i\cup F_i)-r_M(F_i)\right]\nonumber\\
&=&r_{M\contract\mathcal{F}}(S).
\end{eqnarray}
Here the first equality follows from Lemma \ref{contract1} and the second equality is the assumption made in the proposition.
\end{proof}

\section{Algorithm for maximum weight perfect fractional matching}
Let $M$ be a matroid with ground set $E$ and let $L$ be a finite set of lines in $M$. Let $w:L\to \Q_+$ be nonnegative rational weights on the lines. We will assume that $(M,L)$ has a perfect fractional matching.

Throughout the algorithm we keep a chain $\mathcal{F}=\{F_1,\ldots,F_k\}$ of flats in $M$, with $\emptyset\subset F_1\subset\cdots\subset F_k\subset E$. For convenience we always define $F_0:=\emptyset$ and $F_{k+1}:=E$. We also keep a dual feasible solution $y$ with support $\mathcal{F}$ or $\mathcal{F}\cup\{E\}$. That is $y=\lambda_1F_1+\cdots+\lambda_kF_k+\lambda E$ satisfies $a(y)\geq w$, $\lambda_1,\ldots,\lambda_k\in \Q_{>0}$ and $\lambda\in \Q$.

Observe that for a perfect fractional matching $x$ in $(M,L)$ we have:
\begin{eqnarray}
wx=\sum_{l\in L}w_lx_l&\leq &\sum_{l\in L}a(y)_lx_l\nonumber\\
&=&\sum_{i=1}^k \lambda_i a(F_i)x + \lambda a(E)x\nonumber\\
&\leq &\sum_{i=1}^k \lambda_i r(F_i) +\lambda r(E)=r(y).
\end{eqnarray}
Here the equality $a(E)x=r(E)$ is used in the last line. It follows that $x$ has maximum weight if and only if
\begin{eqnarray}
w_l=a(y)_l &\text{ for all }& l\in \supp(x),\label{slack1}\\
a(F)x=r(F) &\text{ for all }& F\in \supp(y).\label{slack2}
\end{eqnarray}
Denote $L_y:=\{l\in L\mid w_l=a(y)_l\}$. The above two conditions will be met once we find a perfect fractional matching $x$ in $(M\contract \mathcal{F},L_y)$. Indeed, in that case $x$ is also a perfect fractional matching in $(M,L)$ by Proposition \ref{liftx}. Equalities (\ref{slack1}) will be satisfied by definition of $L_y$, and equalities (\ref{slack2}) will be satisfied because $a(E)x=r(E)$ implies that for every $i$
\begin{eqnarray}
r(E)=a(E)x&=& a(F_i)x+a(E\setminus F_i)x\nonumber\\
&\leq&r_{M\contract\mathcal{F}}(F_i)+r_{M\contract\mathcal{F}}(E\setminus F_i)\nonumber\\
&=&r(F_i)+(r(E)-r(F_i))\nonumber\\
&=&r(E),
\end{eqnarray}
and hence $a(F_i)=r(F_i)$. The description of the algorithm is as follows.

Initially, we set $\mathcal{F}:=\emptyset$, $y:=\lambda E$, where $\lambda:=\frac{1}{2}\max \{w_l \mid l\in L\}$. The iteration of the algorithm is as follows.

Find a maximum size fractional matching $x$ in $(M\contract \mathcal{F},L_y)$, and find the dominant cover $\frac{1}{2}(S^*+T^*)$, of $(M\contract \mathcal{F},L_y)$. This can be done by the algorithm from \cite{FMM-algorithm}. Now consider two cases.

\textbf{Case 1:} If $x$ is a \emph{perfect} fractional matching, $x$ will be a maximum weight perfect fractional matching in $(M,L)$ and $y$ is an optimal dual solution. We output $x$ and $y$ and stop.

\textbf{Case 2:} If $x$ is not perfect, write $S^*=S^*_0\cup\cdots \cup S^*_k$ and $T^*=T^*_0\cup\cdots\cup T^*_k$, where $S^*_i,T^*_i\subseteq F_{i+1}\setminus F_i$ for $i=0,\ldots,k$. We define
\begin{equation}
z:=\sum_{i=0}^k (S^*_i\cup F_i-F_i)+\sum_{i=0}^k (T^*_i\cup F_i-F_i)- E.
\end{equation}
Observe that $a(z)_l=a(S^*+T^*)_l-2\in \{-2,-1,0,1,2\}$ for every $l\in L$. In particular, $a(z)_l\geq 0$ for $l\in L_y$ and $a(z)_l=0$ for $l\in \supp (x)$.

Let
\begin{eqnarray}
\epsilon_1&:=& \max \{t\geq 0 \mid (y+tz)_F\geq 0 \text{ for all $F\not= E$}\},\nonumber\\
\epsilon_2&:=& \max \{t\geq 0 \mid a(y+tz)\geq w\},
\end{eqnarray}
and let $\epsilon$ be the minimum of $\epsilon_1$ and $\epsilon_2$. Let $y':=y+\epsilon z$ and $\mathcal{F}':=\supp(y')\setminus \{E\}$. By definition of $\epsilon$, $y'$ will be a dual feasible solution. We reset $y:=y'$ and $\mathcal{F}:=\mathcal{F}'$ and iterate.

\subsection*{Finding a maximum weight fractional matching}
The algorithm for finding a maximum weight \emph{perfect} fractional matching described above, can be used to find a maximum weight fractional matching as follows.

Let the matroid $M$, a set of lines $L$ and nonnegative weights $w:L\to \N$ be given. Let $B$ be a base of $M$. By introducing parallel copies if necessary, we may assume that $\{b\}\not\in L$ for every $b\in B$. We define $L':=L\cup \{\{b\},b\in B\}$ and $w':L'\to \N$ by $w'(l):=w(l)$ for $l\in L$ and $w'(\{b\}):=0$ for $b\in B$.

Let $x$ be a vertex of the fractional matroid matching polytope for $(M,L)$, and $B'\subset B$ be a base of $M/\cl(x)$. Define $x':L'\to \{0,\frac{1}{2},1\}$ by $x'_l:=x_l$ for $l\in L$, $x'_{\{b\}}:=\frac{1}{2}$ for $b\in B'$ and $x'_{\{b\}}:=0$ for $b\in B\setminus B'$. It follows from Theorem \ref{closure} that $x'$ is a perfect fractional matching in $(M,L')$.

It follows that the fractional matchings in $(M,L)$ are precisely the restrictions to $L$, of the perfect fractional matchings in $(M,L')$. Using the above algorithm we find a maximum $w'$-weight perfect fractional matching $x'$ in $(M,L')$ and an optimal dual solution $y'$. Restricting $x'$ to $L$ gives the required maximum $w$-weight fractional matching in $(M,L)$. Since $a(y')_{\{b\}}\geq w'(\{b\})=0$ for every $b\in B$, it follows from the fact that $\supp (y')$ is a chain, that $y'_E\geq 0$ and hence is an optimal dual solution for the problem of finding a maximum weight fractional matching in $(M,L)$.

\section{Running time of the algorithm}
In this section, we will show that the algorithm for maximum weight perfect matching described in the previous section terminates after $O(r^3)$ iterations. To this end, we will define a parameter $\psi(\mathcal{F}, S^*,T^*)$ that measures the progress made.

Let $\mathcal{F}=\{F_1, \ldots, F_k\}$ be a chain of flats in $M$, where $\emptyset=:F_0\subset F_1\subset\cdots\subset F_k\subset F_{k+1}:=E$. For a subset $X=X_0\cup\cdots\cup X_k$ of $E$ where $X_i\subseteq F_{i+1}\setminus F_i$ ($i=0,\ldots,k$), we define
\begin{equation}
\phi(\mathcal{F},X):=\sum_{i=0}^k \left[r(F_i\cup X_i)^2-r(F_i)^2\right].
\end{equation}

Observe that $\phi(\mathcal{F},X)$ is a nonnegative integer no larger than $r(E)^2$. Clearly, for $X\subseteq X'$ we have $\phi(\mathcal{F},X)\leq \phi(\mathcal{F},X')$ and $\phi(\mathcal{F},X)=\phi(\mathcal{F},X\contract\mathcal{F})$.

For flats $S$ and $T$ of $M$, we define
\begin{equation}
\psi(\mathcal{F},S,T):=\phi(\mathcal{F},S)+\phi(\mathcal{F},T)+2r(E)r_{M\contract \mathcal{F}}(T).
\end{equation}
So $\psi(\mathcal{F},S,T)$ is a nonnegative integer no larger than $4r(E)^2$.
The following two lemmas will display some useful properties of $\phi$ (and hence of $\psi$).

\begin{lemma}\label{psi1}
Let $X\subseteq X'$ be subsets of $E$. Then
\begin{equation}
\phi(\mathcal{F},X')-\phi(\mathcal{F},X)\leq (r_{M\contract\mathcal{F}}(X')-r_{M\contract\mathcal{F}}(X))\cdot 2r(E),
\end{equation}
and equality holds if and only if $r_{M\contract\mathcal{F}}(X')=r_{M\contract\mathcal{F}}(X)$.
\end{lemma}
\begin{proof}
Write $X=X_0\cup\cdots\cup X_k$ and $X'=X'_0\cup\cdots\cup X'_k$ where $X_i\subseteq X'_i\subseteq F_{i+1}\setminus F_i$. We have
\begin{eqnarray}
\phi(\mathcal{F},X')-\phi(\mathcal{F},X)&=&\sum_{i=0}^k (r(F_i\cup X'_i)^2-r(F_i\cup X_i)^2)\nonumber\\
&=&\sum_{i=0}^k (r(F_i\cup X'_i)-r(F_i\cup X_i))(r(F_i\cup X'_i)+r(F_i\cup X_i))\nonumber\\
&\leq&\sum_{i=0}^k (r(F_i\cup X'_i)-r(F_i\cup X_i))\cdot 2r(E)\nonumber\\
&=&(r_{M\contract\mathcal{F}}(X')-r_{M\contract\mathcal{F}}(X))\cdot 2r(E).
\end{eqnarray}
Equality holds if and only if for every $i$ we have $r(F_i\cup X'_i)=r(F_i\cup X_i)$.
\end{proof}

\begin{lemma}\label{psi2}
Let $X=X_0\cup\cdots\cup X_k$ with $X_i\subseteq F_{i+1}\setminus F_i$, and let $\mathcal{F}'\supset \mathcal{F}$ be a longer chain of flats in $M$. Suppose that $r_{M\contract \mathcal{F}}(X)=r_{M\contract\mathcal{F'}}(X)$. Then $\phi(\mathcal{F},X)\leq \phi(\mathcal{F'},X)$, and equality holds if and only if $\mathcal{F'}\cup\{F_i\join X_i, i=0,\ldots, k\}$ is a chain.
\end{lemma}
\begin{proof}
Consider a fixed $i\in \{0,\ldots, k\}$. Let $H_0\subset\cdots\subset H_{l+1}$ be the flats $\{F\in \mathcal{F'}\mid F_{i}\subseteq F\subseteq F_{i+1}\}$. Write $X_i:=Y_0\cup\cdots\cup Y_l$ where $Y_j\subseteq H_{j+1}\setminus H_j$ for $j=0,\ldots,l$. Denote $r:=r(F_i\cup X_i)-r(F_i)$ and $r_j:=r(H_j\cup Y_j)-r(H_j)\leq r(H_{j+1})-r(H_j)$ for $j=0,\ldots,l$.

The assumpion $r_{M\contract \mathcal{F}}(X)=r_{M\contract \mathcal{F'}}(X)$ implies that $r=r_0+\cdots+r_l$. We have the following inequalities.
\begin{eqnarray}
r(F_i\cup X_i)^2-r(F_i)^2&=&(r(F_i)+r)^2-r(F_i)^2\nonumber\\
&=& \sum_{j=0}^l \left[ (r(F_i)+r_0+\cdots+r_{j-1}+r_j)^2-(r(F_i)+r_0+\cdots+r_{j-1})^2\right]\nonumber\\
&\leq &\sum_{j=0}^l \left[ (r(H_j)+r_j)^2-r(H_j)^2\right]\nonumber\\
&=&\sum_{j=0}^l (r(H_j\cup Y_j)^2-r(H_j)^2).
\end{eqnarray}
The inequality follows from the fact that $r(H_j)\geq r(F_i)+r_0+\cdots+r_{j-1}$ for $j=0,\ldots,l$, and equality holds if and only if for every $j$ either $r(H_j)=r(F_i)+r_0+\cdots+r_{j-1}$ or $r_j=0$. That is, if $j$ is the largest index for which $r_j>0$, then we have equality if and only if $H_j\subseteq F_i\join X_i\subseteq H_{j+1}$.
Summing over all $i$ proves the lemma.
\end{proof}

In the remainder of this section, we will prove that the algorithm described in the previous section is correct, and that the number of iterations is at most $O(r(E)^3)$.

\begin{proof}[Proof of the running time bound]
We will show that the pair of nonnegative integers $(r(E)-2\nu^*(M\contract\mathcal{F},L_y),\ \psi(\mathcal{F},S^*,T^*))$ decreases lexicographically in each iteration.

Consider an iteration. Let $y$ be the current dual solution, $\mathcal{F}$ the current chain of flats in $M$ and let $\frac{1}{2}(S^*+T^*)$ be the dominant cover of $(M\contract \mathcal{F}, L_y)$. Denote by $y'$, $\mathcal{F}'$ and $\frac{1}{2}({S^*}'+{T^*}')$ the corresponding objects in the next iteration.

We define the subset $\overline{L}$ of lines by
\begin{eqnarray}
\overline{L}&:=&\{l\in L_y\mid l\in \supp(x)\nonumber\\
&&\text{ for some maximum size fractional matching $x$ in $(M\contract\mathcal{F},L_y)$ }\},
\end{eqnarray}
and the chain $\overline{\mathcal{F}}$ of flats in $M$ by
\begin{equation}
\overline{\mathcal{F}}:=\mathcal{F}\cup \{S^*_i\cup F_i, i=0,\ldots, k\} \cup \{T^*_i\cup F_i, i=0,\ldots, k\},
\end{equation}
where $S^*_i:=S^*\cap (F_{i+1}\setminus F_i)$ and $T^*_i:=T^*\cap (F_{i+1}\setminus F_i)$ for $i=0,\ldots, k$. Note that $\overline{\mathcal{F}}=\mathcal{F}\cup\mathcal{F}'$, and hence $M\contract \overline{\mathcal{F}}=(M\contract \mathcal{F})\contract \mathcal{F}'=(M\contract\mathcal{F}')\contract \mathcal{F}$.

By complementary slackness, $a(\frac{1}{2}(S^*+T^*))_l=2$ holds for every $l\in \overline{L}$. Therefore we have $a(z)_l=0$ for every $l\in \overline{L}$ so that
\begin{equation}
\overline{L}\subseteq L_{y'}.
\end{equation}

Again by complementary slackness, $a(S^*)x=r_{M\contract\mathcal{F}}(S^*)$ and $a(T^*)x=r_{M\contract\mathcal{F}}(T^*)$ holds for any maximum size fractional matching $x$ in $(M\contract\mathcal{F}, L_y)$. Hence it follows by Proposition \ref{liftx} that
$x$ is also a fractional matching in $(M\contract \overline{\mathcal{F}},\overline{L})$ and hence in $(M\contract \mathcal{F}',L_{y'})$. We can conclude that
\begin{equation}\label{nuincrease}
\nu^*(M\contract \mathcal{F},L_y)=\nu^*(M\contract \overline{\mathcal{F}},\overline{L})\leq \nu^*(M\contract \mathcal{F'},L_{y'}).
\end{equation}
When strict inequality holds in (\ref{nuincrease}), we are done. Therefore, in the remainder of the proof, we may assume that
\begin{equation}
\nu^*(M\contract \mathcal{F},L_y)=\nu^*(M\contract \mathcal{F'},L_{y'}).
\end{equation}
Denote
\begin{equation}
\overline{S}:={S^*}'\contract \overline{\mathcal{F}},\quad \overline{T}:={T^*}'\contract \overline{\mathcal{F}}.
\end{equation}

Since
\begin{eqnarray}
\nu^*(M\contract \overline{\mathcal{F}}, \overline{L})&\leq&\nu^*(M\contract \overline{\mathcal{F}}, L_{y'})\\
&\leq &\frac{1}{2} r_{M\contract \overline{\mathcal{F}}}(\overline{S}+\overline{T})\\
&\leq& \frac{1}{2} r_{M\contract\mathcal{F}'}({S^*}'+{T^*}')\\
&=&\nu^*(M\contract\mathcal{F}',L_{y'})=\nu^*(M\contract\overline{\mathcal{F}},\overline{L}),
\end{eqnarray}
we find that $\frac{1}{2}(\overline{S}+\overline{T})$ is a minimum cover in $(M\contract \overline{\mathcal{F}},L_{y'})$, and hence also in $(M\contract\overline{\mathcal{F}},\overline{L})$.

Clearly, $\frac{1}{2}(S^*+T^*)$ is also a minimum cover of $(M\contract\overline{\mathcal{F}},\overline{L})$. Furthermore, since $x$ is a maximum size fractional matching in $(M\contract \mathcal{F},L_y)$ if and only if $x$ is a maximum size fractional matching in $(M\contract \overline{\mathcal{F}},\overline{L})$, it follows that $\frac{1}{2}(S^*+T^*)$ is in fact the dominant cover of $(M\contract\overline{\mathcal{F}},\overline{L})$. Indeed, let $\frac{1}{2}(S+T)$, $S\subseteq T$ be the dominant cover of $(M\contract\overline{\mathcal{F}},\overline{L})$. It suffices to show that $T^*=T$. For every maximum size fractional matching $x$ in $(M\contract\mathcal{F},L_y)$, we have $\cl_{M\contract\mathcal{F}}(x)\supseteq T^*$. This implies that $\cl_{M\contract\mathcal{F}}(x)$ is also a flat in $M\contract\overline{\mathcal{F}}$, and hence $\cl_{M\contract\mathcal{F}}(x)=\cl_{M\contract\overline{\mathcal{F}}}(x)$. By the characterization of the dominant cover, Theorem \ref{dominant}, it now follows that
\begin{equation}
T=\bigcap_x \cl_{M\contract\overline{\mathcal{F}}}(x)=\bigcap_x\cl_{M\contract\mathcal{F}}(x)=T^*,
\end{equation}
where the intersection runs over all maximum size fractional matchings $x$ in $(M\contract\mathcal{F},L_y)$.

By comparing the two covers of $(M\contract \overline{\mathcal{F}},\overline{L})$, we obtain
\begin{equation}\label{comparecover}
S^*\subseteq \overline{S},\quad \overline{T}\subseteq T^*.
\end{equation}

Note that $r_{M\contract \mathcal{F}'}({S^*}')= r_{M\contract \overline{\mathcal{F}}}({S^*}')$, $r_{M\contract \mathcal{F}'}({T^*}')= r_{M\contract \overline{\mathcal{F}}}({T^*}')$, and
$r_{M\contract\overline{\mathcal{F}}}(\overline{S}-S^*+\overline{T}-T^*)=0$, thus by Lemma \ref{psi2} and Lemma \ref{psi1} we get that

\begin{eqnarray}\label{comparepsi}
\psi(\mathcal{F'},{S^*}',{T^*}')&\leq&\psi(\overline{\mathcal{F}},\overline{S},\overline{T})\nonumber\\
&=&\phi(\overline{\mathcal{F}},\overline{S})+\phi(\overline{\mathcal{F}},\overline{T})+2r(E)r_{M\contract\overline{\mathcal{F}}}(\overline{T})\nonumber\\
&\leq & \phi(\overline{\mathcal{F}},S^*)+\phi(\overline{\mathcal{F}},T^*)+2r(E)r_{M\contract\overline{\mathcal{F}}}(\overline{T}+\overline{S}-S^*)\nonumber\\
&=&\phi(\overline{\mathcal{F}},S^*)+\phi(\overline{\mathcal{F}},T^*)+2r(E)r_{M\contract\overline{\mathcal{F}}}(T^*)\nonumber\\
&=&\psi(\overline{\mathcal{F}},S^*,T^*)\nonumber\\
&=&\psi(\mathcal{F},S^*,T^*).
\end{eqnarray}

We need to show that $\psi(\mathcal{F'},{S^*}',{T^*}')<\psi(\mathcal{F},S^*,T^*)$ holds. Suppose that equality holds in the second inequality in (\ref{comparepsi}). Then we must have equality in (\ref{comparecover}), by Lemma \ref{psi1}. This means that we are in the case $\epsilon_1<\epsilon_2$. Indeed, if $\epsilon_1\geq \epsilon_2$, there exists an $l\in L_{y'}\setminus L_y$ with $a(S^*+T^*)_l<2$. However, $a(\overline{S}+\overline{T})_l=2$, which would imply that we do not have equality in (\ref{comparecover}).

Since $\epsilon_1<\epsilon_2$, there is an $F_i\in \mathcal{F}\setminus \mathcal{F'}$.  Since $z_{F_i}<0$, we have either ($S^*_i\not=\emptyset$ and $S^*_{i-1}\not\supseteq F_i\setminus F_{i-1}$) or ($T^*_i\not=\emptyset$ and $T^*_{i-1}\not\supseteq F_i\setminus F_{i-1}$).

Now let $\mathcal{F}'=\{F'_1,F'_2,\cdots ,F'_m\}$, and choose $j$ such that $F'_j\subsetneq F_i\subsetneq F'_{j+1}$.

First, assume that $S^*_i\not=\emptyset$ and $S^*_{i-1}\not\supseteq F_i\setminus F_{i-1}$. Then we apply Lemma \ref{psi2} with respect to $\mathcal{F}'$ and $\overline{\mathcal{F}}$, and $X:=S^*=\overline{S}$. Note that $F'_j\join X_j=F'_j\join \overline{S}_i$. Since $\{F'_j\join \overline{S}_i\}\cup \overline{\mathcal{F}}$ is not a chain, we get that $\phi (\mathcal{F}',{S^*}')<\phi (\overline{\mathcal{F}},\overline{S})$, and thus, $\psi(\mathcal{F'},{S^*}',{T^*}')<\psi(\mathcal{F},S^*,T^*)$.

Second, assume that $T^*_i\not=\emptyset$ and $T^*_{i-1}\not\supseteq F_i\setminus F_{i-1}$. Here, if $S^*_i\neq\emptyset$, then the first case applies, thus we may also assume that $S^*_i=\emptyset$. Apply Lemma \ref{psi2} with respect to $\mathcal{F}'$ and $\overline{\mathcal{F}}$, and $X:=T^*=\overline{T}$. Note that $F'_j\join X_j=F'_j\join \overline{T}_i$. Since $\{F'_j\join \overline{T}_i\}\cup \overline{\mathcal{F}}$ is not a chain, we get that $\phi (\mathcal{F}',{T^*}')<\phi (\overline{\mathcal{F}},\overline{T})$, and thus, $\psi(\mathcal{F'},{S^*}',{T^*}')<\psi(\mathcal{F},S^*,T^*)$.

\end{proof}

\section*{Acknowledgements}
The first author would like to thank Rudi Pendavingh for stimulating discussions on a possible weighted version of the fractional matching algorithm for matroids.


TITLE: Vectors in elementary physics vs vectors in linear algebra
QUESTION [5 upvotes]: I am taking a linear algebra course as well as an introductory physics course, and I am confused about how vectors in each are the same and different.
First, why is it that in physics, magnitude and direction of vectors are emphasized while in linear algebra components of vectors are emphasized? Also, for elementary physics (kinematics, dynamics) is $\Re^{2}$ and $\Re^{3}$ the vector space from which we operate? Finally, in physics, it is emphasized that vectors are particularly useful because they are not tied to any one coordinate system. What does this mean exactly? In linear algebra we always write vectors emanating from the origin of the coordinate system, so it would seem as though the vectors are tied to the coordinate system.

REPLY [1 votes]: In the linear algebra found in Michael Artin's Algebra, coordinates are not emphasized*.
You have a field (like $\mathbb{R}$ or $\mathbb{C}$), and your vector space (like $\mathbb{R}^n$ or $\mathbb{C}^n$) which you can multiply by elements of your field. This has to satisfy some big list of axioms, but no axiom mentions coordinates. $\mathbb{R}^n$, consisting of lists of real $n$-tuples, is an example of a vector space, but you could imagine defining it without making use of coordinates. You can define the dimension of the vector space without making use of coordinates either: the dimension is the size of the largest possible set of linearly independent vectors. So there's no coordinate dependence here.
In linear algebra, you can continue using abstract definitions. You care about linear operators on vector spaces. Linear maps have their own abstract definition. Once you choose a basis, composition of linear maps turns into matrix multiplication! So there doesn't have to be any coordinate dependence here either.
But even with all of this coordinate-free stuff, we still don't have the "coordinate-free" nature that physicists care about. We actually have to throw geometry in to get anything useful for physics. In classical mechanics, we throw in Euclidean geometry.
The simplest way to throw in Euclidean geometry is to... use coordinates. We could say that vectors $(x,y)$ have length $\sqrt{x^2+y^2}$ (Note: normally this is the pythagorean theorem and is a "theorem". Here it's an axiom), and that the angle between two vectors satisfies $(v_x,v_y)\cdot(w_x,w_y)=v_x w_x+v_y w_y=\|v\|\|w\|\cos(\theta)$. This turns the vector space into an inner product space, but we still don't have quite enough for physics, just yet. To get something more physical: dictate that all of our physical laws have to be invariant under transformations which leave all lengths and angles unchanged.
Finally, under the structure of a vector space, the Euclidean inner product, and the demand that physics should be unchanged under all linear maps that leave the inner product conserved, we have something resembling a vector in physics.
The moral is that it's a pain in the butt to spell out all of the mathematical assumptions. The vectors in mathematics are precisely anything that satisfied the vector axioms I linked above. The vectors in physics have tons of extra structure on them - like, for velocity vectors in classical mechanics, Euclidean geometry. However this doesn't necessarily have anything to do with coordinates.


TITLE: Odd factorisation of Indicies?
QUESTION [0 upvotes]: I'm sorry for the terrible formatting, I'm sorta new so I don't know how to use MathJax very well :( see below for my first attempt :)
I came across the indical expression : $$\frac{x-1}{x-x^{1/2}-2}$$
When I first saw this expression I thought this was the final answer, however it apparently can be simplified to: $$\frac{x^{1/2}-1}{x^{1/2}-2}$$
However I struggle so see how the factorization in this equation is done as my various attempts have resulted in more complicated or wrong expressions. However I have substituted values and the answer is right. If you could please explain the factorization/steps required I would be very thankful :)

REPLY [0 votes]: I wish to help out the community by making it clear that this question has been answered by the commentor Lubin where the trick was to "Substitute x=t^2 and it should fall out".
Thank you Lubin :)


TITLE: Strictly increasing function value
QUESTION [1 upvotes]: Question: Let $f(x): N → N$ be a strictly increasing function, where $N$ is denoted as the set of all positive
integers. If $f(f(n)) = 3n$, what is a possible value of $f(1)$?
My approach (Cases) :

$f(1) = 1$: Starting to eliminate some possible values for $f(1),$ we realize that $f(1)$ is not equal to $1$, because otherwise $f(f(1)) = 1$, but according to the problem, it would have to be $3$. Since $1$ is not equal to $3$, $f(1)$ is not equal to $1$.

$f(2) = 2$: There is nothing wrong with $f(2) = 2$ because it satisfies the strictly increasing part and it also doesn't have a problem with $f(f(2)) = 6$, although I could be wrong.

$f(3) = 3$: $f(f(n)) = 9$... what to do?

I am very confused from this point onwards because I don't know how to use the fact that $f(x)$ is a strictly increasing function, or what to do with the $f(f(n)) = 3n$. Maybe I could use the $N$ is the set of all positive integers? I don't know.
Any help would be appreciated, thank you!

REPLY [2 votes]: $f$ strictly increasing means that $f(n)<f(n+1)$. Most of the proof follows from this.
As you have said, $f(1)\neq 1$ since if $f(1)=1$ then $f(f(1))=f(1)=1$ but we require $f(f(1))=3$. So $f(1)>1$.
Now if $f(1)>2$ then $f(2)>3$ (since $f$ is strictly increasing) so $f(f(1))>f(2)>3$ although we again require $f(f(1))=3$.
So we have discounted, by contradiction, every possibility except $f(1)=2$


TITLE: Show that, for any $\epsilon>0$, there exist two rationals such that $q < x < q'$ and $|q-q'|<\epsilon$
QUESTION [2 upvotes]: I think I have the first part, as I have shown that $q < q + (q'-q)/2 < q'$, but I have trouble in proving that $|q-q'|< \epsilon$.  Could someone tell me if there is a better way of showing the first part and how to show the second part?
For those asking x is a real number

REPLY [2 votes]: I hope you can use the fact that given $a,b \in \Bbb R$ with $a < b$, there is a rational number between $a$ and $b$. Then see how you can use this fact.