TITLE: On the continuity of functions.
QUESTION [0 upvotes]: Examine the continuity of these functions on $[0,1]$
$a)$ $f(x)=\frac{\sin{\frac{1}{x^2}}}{x^2}$ if $x \neq 0$ and $f(0)=0$
$b)$ $g(x)=x (-1)^{[\frac{1}{x}]}$ if $x \neq 0$ and $g(0)=0$
$[x]$ is the integer part of $x$

For the first function:
It is continuous for $x \neq 0$
For $x=0$ we consider the sequences $x_n=\frac{1}{\sqrt{2n \pi+ \frac{\pi}{2}}} \to 0$ and $f(x_n) \to + \infty $
So $f$ is not continuous at $0$
Now the second function is more tricky and i would like someone to help me verify my reasoning.
For $x=0$ we have that $|f(x)| \leq |x| \to 0=f(0)$ thus $f$ is continuous at zero.
Now assume that we take for instance $x= \frac{1}{2}$
$$\lim_{x \to \frac{1}{2}^-}f(x)= \frac{1}{2}$$
because if $x \to \frac{1}{2}^-$ then $[\frac{1}{x}] \to 2^+$ thus conider $A=\{x\in [0,1]| 2<\frac{1}{x}<3\}$ and if $x \in A$ then $[\frac{1}{x}]=2 \to 2$
so $\lim_{x \to \frac{1}{2}^-}f(x)= \frac{1}{2}$
Also using the previous  argument we can see that $\lim_{x \to \frac{1}{2}^+}f(x)=- \frac{1}{2}$
So the limit of $f$ at this point does not exist thus $f$ is not continuous.
Is my reasoning correct?
Also can we say that the last function is discontinuous on the set $B=\{\frac{1}{n}|n \in \mathbb{N}\}$?
Thank you in advance.

REPLY [1 votes]: You can even generalize it let it be tending towards $\frac {1}{n} $ so from RHS we will have$ [n+h]=n $ and from LHS we will have $[n-h]=n-1$ now for any integer(positive or negative not only natural numbers except $0$) we will have $(-1)^n\neq (-1)^{n-1} $ hence the function is discontinuous at every $\frac {1}{n} $ where $n $ is an integer except $0$


text:
\begin{document}
\baselineskip=18pt
\renewcommand{\thefootnote}{}

\title{Counting Primes, Groups and Manifolds}
\author{Dorian Goldfeld$^1$, Alexander Lubotzky$^2$,\\ Nikolay Nikolov$^3$ and L\'{a}szl\'{o} Pyber$^4$}
\maketitle

\textbf{Addresses:}

\textbf{1.} Department of Mathematics, Columbia University, New York, NY 10027, U.S.A.,

\textbf{2.} Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel,

\textbf{3.} Tata Institute for Fundamental Research, Colaba, Mumbai 400005, India,

\textbf{4.} A. R\'{e}nyi Institute of Mathematics, Re\'{a}ltanoda ut. 13-15, H-1053, Budapest, Hungary.

\textbf{Corresponding author:} Alexander Lubotzky, tel +972 2 6584387, e-mail: alexlub@math.huji.ac.il .

\textbf{Pages: 11 (double spaced).}

\textbf{Wordcount: abstract 150, main text 2200.}

\textbf{ PNAS Classification.} Physical sciences: Mathematics.

\emph{2000 Mathematics Subject Classification 20H05; 22E40}

\newpage

\section*{Abstract}
Let $\Lambda = \mathrm{SL}_2(\Bbb Z)$ be the modular group
and let $c_n(\Lambda)$ be the number of congruence subgroups of $\Lambda$
of index at most $n$. We prove that  $\lim\limits_{n\to \infty}
\frac{\log c_n(\Lambda)}{ (\log n)^2/\log\log n} =
\frac{3-2\sqrt{2}}{4}.$ The proof
is based on the Bombieri-Vinogradov `Riemann hypothesis on the average' and on the solution of a new type
of extremal problem in combinatorial number theory. Similar surprisingly sharp estimates are obtained for the subgroup growth of lattices in higher rank semisimple Lie groups. If $G$ is such a Lie group and $\Gamma$ is an irreducible lattice of $G$ it turns out that the subgroup growth of $\Gamma$ is independent of the lattice and depends only on the Lie type of the direct factors of $G$. It can be calculated easily from the root system. The most general case of this result relies on the Generalized Riemann Hypothesis but many special cases are unconditional. The proofs use techniques from number theory, algebraic groups, finite group theory and combinatorics.

\newpage

\section*{Statement of results: arithmetic groups}
Let $n$ be a large integer, $\Gamma$ a finitely generated group
and $M$ a Riemannian manifold.  Denote by $\pi(n)$ the number of
primes less or equal to $n$, $s_n(\Gamma)$ is the number of
subgroups of $\Gamma$ of index at most $n$ and $b_n (M)$ is the
number of covers of $M$ of degree at most $n$.  The aim of this
note is to announce results which show that in some
circumstances, these three seemingly unrelated functions are very
much connected.  This happens, for example, when $\Gamma$ is an
arithmetic group, in which case it is also the fundamental group
of a suitable locally symmetric finite volume manifold $M$.  The
studies of $s_n(\Gamma)$ and $b_n (M)$ are then almost the same.
Moreover, if $\Gamma$ has the congruence subgroup property then
estimating $s_n(\Gamma)$ boils down to counting congruence
subgroups of $\Gamma$. The latter is intimately related to the
classical problem of counting primes.
To present our results we need more notation.

Let $G$ be an absolutely
simple, connected, simply connected algebraic group defined over a
number field $k$. For a finite subset of valuations of $k$
including all the archimedean ones, let $\mathcal{O}_S$ denote the
ring of $S$-integers of $k$ and set $\Gamma =G(\mathcal{O}_S)$. A
subgroup $H \leq \Gamma$ is called a congruence subgroup if there
is some ideal $I \vartriangleleft \mathcal{O}_S$ such that $H$
contains the kernel of the homomorphism $\Gamma \rightarrow
G(\mathcal{O}_S/I)$.

Let $c_n(\Gamma)$ denote the number of congruence subgroups of
index at most $n$ in $\Gamma$. The counting of congruence
subgroups in arithmetic groups has already played a role in the
proof of one of the main results of the theory of subgroup growth:
A finitely generated residually finite group $\Gamma$ has
polynomial subgroup growth (i.e. $s_n(\Gamma) = n^{O(1)}$) if and
only if $\Gamma$ is virtually solvable of finite rank (cf.
\cite{LS} and the references therein).  That theorem required
only a weak lower bound on the number congruence subgroups.  In
\cite{lub} Lubotzky proved a more precise result: there exist
numbers $a,b$ depending on $G,k$ and $S$, such that$^*$
\footnotetext{$^*$ The lower bound depended on GRH at the time but
was made unconditional in \cite{GLP}} \[ n^{\frac{a \log n}{\log
\log n}} \leq c_n(\Gamma) \leq n^{\frac{b \log n}{\log \log n}},\]
and, moreover the sequence $s_n(\Gamma)$ has much faster growth
(at least $n^{\log n}$) if the congruence subgroup property fails
for $G$. Below we determine the precise rate of growth of
$c_n(\Gamma)$. (All logarithms are in base $e$.)\medskip

Let $X$ be the Dynkin diagram of the split form of $G$ (e.g. $X=A_{n-1}$ if $G=\mathrm{SU}_n$).
Let $h$ be the Coxeter number of the root system $\Phi$ corresponding to $X$ (it is the order of the Coxeter element of the Weyl group of $X$). Then $h=\frac{|\Phi|}{l}$ where $l= \mathrm{rank}_\mathbb{C}(G)= \mathrm{rank}(X)$, and for later use define $R:=h/2$. Let
\[\gamma(G)=\frac{ (\sqrt{h(h+2)}-h)^2}{4h^2}. \]

Let GRH denote the Generalized Riemann Hypothesis for Artin-Hecke
$L$-functions of number fields as stated in \cite{Weil}. The GRH
implies in particular:

Let $k$ be a Galois number field of degree $d$ over the rationals and
let $q$ be a prime such that the cyclotomic field of $q$-th roots of unity is disjoint from $k$.  Denote by $\pi_k(x, q)$ the number of primes
$p$ with $p \le x, \; p \equiv 1(\mod q)$ and $p$ splits
completely at $k$.  Then
\[
\left| \pi_k (x, q) - \frac{x}{d \phi(q) \log x}\right| < Cx^{\frac{1}{2}} \log x \log q
\]
for some constant $C=C(k)>0$ depending only on $k$ (a more precise bound is given in \cite{mms}). \bigskip

The lower bound for the limit in the following Theorem was proved in \cite{GLP} and the upper bound in \cite{LN}:

\begin{theorem}\label{arithmetic} Let $G$, $\Gamma$ and $\gamma(G)$ be as defined above. Assuming GRH we have
\[ \lim_{n \rightarrow \infty} \frac{\log c_n(\Gamma)}{(\log n)^2/ \log \log n}= \gamma(G),\] and moreover, this result is unconditional if $G$ is of inner type (e.g. $G$ splits) and $k$ is either an abelian extension of $\mathbb{Q}$ or a Galois extension
of degree less than 42. \end{theorem} \medskip

An interesting aspect
of this theorem is not only that the limit exists but that it is completely
independent of $k$ and $S$, and depends only on $G$. While the
independence on $S$ is a minor point and can be proved directly, the only way
we know to prove the independence on $k$ is by applying the whole machinery
of the proof.

In \cite{GLP} the crucial special case of $\Gamma=\mathrm{SL}_2(\mathcal{O}_S)$ is proved in full. There we have $\gamma(\mathrm{SL}_2)=\frac{1}{4}(3-2\sqrt{2})$. The lower bound follows using the Bombieri-Vinogradov Theorem \cite{bomb}
and the upper bound by a massive new combinatorial analysis.

\subsection*{Lattices}

Let $H$ be a connected \emph{characteristic 0} semisimple group. By this we mean that $H=\prod_{i=1}^r G_i(K_i)$ where for each $i$, $K_i$ is a local field of characteristic 0 and $G_i$ is a connected simple algebraic group over $K_i$. We assume throughout that none of the factors $G_i(K_i)$ is compact (so that
$\mathrm{rank}_{K_i}(G_i)\geq 1$). Let $\Gamma$ be an irreducible lattice of $H$, i.e. for every infinite normal subgroup $N$ of $H$  the image of $\Gamma$ in $H/N$ is dense there.

Assume now that \[\mathrm{rank}(H):=\sum_{i=1}^r \mathrm{rank}_{K_i}(G_i)\geq 2.\]
By  Margulis' Arithmeticity Theorem
(\cite{margulis}) every irreducible lattice $\Gamma$ in $H$ is arithmetic. Also the split forms of the factors $G_i$ of $H$ are necessarily of the same type and we set $\gamma(H):=\gamma(G_i)$.

Moreover, a famous conjecture of Serre (\cite{serre}) asserts that
such a group $\Gamma$ has the congruence subgroup property. It has been proved in many cases.
This enables us to prove:
\begin{theorem}\label{lat}
Assuming  GRH and Serre's conjecture, then for every non-compact
higher rank characteristic 0 semisimple group $H$ and every irreducible lattice
$\Gamma$ in $H$ the limit \[ \lim\limits_{n\to \infty} \;
\frac{\log s_n(\Gamma)}{(\log n)^2/\log\log n}\] exists and equals
$\gamma(H)$, i.e. it is independent of the lattice $\Gamma$.

Moreover the above holds unconditionally if $H$ is a simple
connected Lie group not locally isomorphic to $D_4(\mathbb{C})$
and $\Gamma$ is a non-uniform lattice in $H$ (i.e. $H/\Gamma$ is
non-compact).
\end{theorem}

Theorem 2 shows, in particular, some algebraic similarity between
different lattices $\Gamma$ in the same Lie group $G$.  This is an
addition to other results in the theory e.g. Furstenberg's theorem
showing that the boundaries of all such $\Gamma$'s are the same or
Margulis super-rigidity, which shows that the finite dimensional
representation theory of the different $\Gamma$'s in the same $G$
are similar.  (cf \cite{margulis} and the references therein).

We point out the following geometric reformulation of the special case:
\begin{theorem}\label{t'} Let $H$ be a simple connected Lie group of $\mathbb{R}$-rank $\geq 2$ which is not locally isomorphic to $D_4(\mathbb{C})$. Put $X=H/K$ where $K$ is a maximal compact subgroup of $H$. Let $M$ be a finite volume non-compact manifold
covered by $X$ and let $b_n (M)$ be the number of covers of $M$ of
degree at most $n$.  Then $\lim\limits_{n\to\infty} \;
\frac{\log b_n(M)}{(\log n)^2/\log\log n}$ exists, equals $\gamma(H)$
and is independent of $M$.
\end{theorem}

It is interesting to compare Theorems 2 and 3 with the results of
Liebeck-Shalev\cite{ls}, and M\"{u}ller-Puchta \cite{MP}: If
$H=\mathrm{SL}_2(\mathbb{R})$ and $\Gamma$ is a lattice in $H$
then $\lim\limits_{n\to \infty} \;\frac{\log s_n(\Gamma)}{\log n!}=-\chi(\Gamma)$, where
$\chi$ is the Euler characteristic. \bigskip

We finally mention a conjecture and a question:  Let $X$ be the
symmetric space associated with a simple Lie group $H$ as in
Theorem 3.  Denote by $m_n(X)$ the number of manifolds covered by
$X$ of volume at most $n$.  By a well known result of Wang \cite{Wang},
this number is finite unless $H$ is locally isomorphic to
$SL_2(\bbr)$ or $SL_2(\bbc)$.

\bigskip
\noindent {\bf Conjecture.} \  If $\mathbb{R}\textrm{-rank}(H) \ge 2$ then
\[
\lim \limits_{n\to \infty} \; \frac{\log m_n(X)}{(\log n)^2/\log\log n} = \gamma(H).
\]

\noindent {\bf Question:} Estimate $m_n(X)$ for the case of $H$
having $\bbr$-rank equal to one.  For $H=\mathrm{SO}(n, 1)$ the results of
\cite{BGLM} suggest that $\lim \limits_{n\to \infty} \; \frac{\log m_n
(H) }{\log n!}$ may exist, but we do not have any clue what it
could be.
\section*{Proofs: the lower bound}
We shall illustrate the main idea of the proof with $\Gamma= \mathrm{SL}_d(\mathbb{Z})$ and refer to \cite{GLP} for the full details.

Choose any $\rho \in (0,\frac{1}{2})$. For $x>>0$ and a prime $q<x$ let $P(x,q)$ be the set of primes $p\leq x$ such that $p \equiv 1$ mod $q$. Let $L(x,q)=|P(x,q)|$ and $M(x,q)= \sum_{p\in P(x,q)} \log p$. Then the Bombieri-Vinogradov Theorem \cite{bomb} ensures the existence of a prime $q \in (\frac{x^\rho}{\log x},x^\rho)$ such that
\[ L(x,q) = \frac{x}{\phi(q) \log x}+O\left(\frac{x}{\phi(q) (\log x)^2}\right) ;\quad M(x,q) = \frac{x}{\phi(q)}+O\left(\frac{x}{\phi(q) (\log x)^2}\right).\]
Put $L:=L(x,q)$ and $M:=M(x,q)$.

By strong approximation  (cf. \cite{LS}, Window 9) $\Gamma$ maps onto \\
$G_P:=\prod_{p\in P(x,q)}\mathrm{SL}_d(\mathbb{F}_p)$. Let $B(p)$
be the subgroup of upper triangular matrices of
$\mathrm{SL}_d(\mathbb{F}_p)$ and set
\[B_P:=\prod_{p\in P(x,q)}B(p).\] The group $B_P$ maps onto the
diagonal $\prod_p (\mathbb{F}^*_p)^{d-1}$ which in turn maps onto
$\mathbb{F}_q^{(d-1)L}$. For fixed $\sigma \in (0,1)\cap
\frac{1}{L(d-1)}\mathbb{N}$ the latter vector space has about
$q^{\sigma (1-\sigma)(d-1)^2 L^2}$ subgroups of index $q^{\sigma
(d-1)L}$ (see Proposition 1.5.2 in \cite{LS}), each giving rise to
a subgroup of index $n=[G_P:B_P]q^{\sigma (d-1)L}$ in $\Gamma$.
Now \\ $\log [G_P:B_P]\sim d(d-1)M/2$ as $x \rightarrow \infty$
and after some algebraic manipulations we obtain that for this
chosen value of $n$
\[\frac{\log c_n(\Gamma)}{(\log n)^2/ \log \log n} \geq\frac{\sigma (1-\sigma)\rho (1-\rho)}{\left(\sigma \rho +R\right)^2} -o(1), \quad (x \rightarrow \infty) \] where in our case $R=d/2$. As shown in \cite{GLP} \S 3 the maximum value of the above expression for $\sigma, \rho \in (0,1)$ is precisely $\gamma (G)=\frac{ (\sqrt{R(R+1)}-R)^2}{4R^2}$ and is achieved for $\sigma_0=\rho_0= \sqrt{R(R+1)}-R$. By taking $x$ sufficiently large we can choose $\sigma \in (0,1)\cap \frac{1}{L(d-1)}\mathbb{N}$ to be arbitrarily close to $\sigma_0$, and take $\rho=\rho_0$. This proves the lower bound.  \medskip

The reason for invoking the GRH in Theorem \ref{arithmetic} is that in the general case we need an equivalent of the Bombieri-Vinogradov theorem for $k$ in place of $\mathbb{Q}$. The work of M.R. Murty and V.K. Murty \cite{murty} gives an analogue of it for number fields but their result is weaker in general. It suffices for our needs when, for example $k/\mathbb{Q}$, is an abelian extension.
\subsection*{The upper bound}
The proof of the upper bound in \cite{LN} is inspired by the special case solved in \cite{GLP} and has two parts:

I. A reduction to an extremal problem for abelian groups, and

II. Solving this extremal problem (Theorem \ref{ab} below).

\textbf{Part I:}

The subgroup structure of the groups $\mathrm{SL}_2(\mathbb{F}_p)$ is completely known. Using
this it is shown in \cite{GLP} that Theorem \ref{arithmetic} for $\mathrm{SL}_2(\mathbb{Z})$ is equivalent to the
following extremal result on counting subgroups of abelian groups:

Let $C_m$ denote the cyclic group of order $m$.
For all pairs $\mathcal{P}_-$ and $\mathcal{P}_+$ of disjoint sets of primes, let \[ f(n):= \max \left \{ s_r(X)\ \left \vert  \quad X= \prod_{p \in \mathcal{P}_-} C_{p-1} \times  \prod_{p \in \mathcal{P}_+} C_{p+1} \right. \right \}, \]
where the maximum is taken over all sets $\mathcal{P}_-, \mathcal{P}_+$ and $r \in \mathbb{N}$ such that \\ $n \geq r \prod_{p \in \mathcal{P}} p$, (here $\mathcal{P}=\mathcal{P}_- \cup \mathcal{P}_+$).
\begin{theorem} We have \[
\limsup_{n \rightarrow \infty} \frac{ \log c_n(\mathrm{SL}_2(\mathbb{Z}))}{(\log n)^2 / \log \log n} = \limsup_{n \rightarrow \infty} \frac{ \log f(n)}{(\log n)^2 / \log \log n}.\]
\end{theorem}

By contrast there is no such precise description of the subgroup structure even for $\mathrm{SL}_n(\mathbb{F}_p)$. Still, surprisingly, the proof of the general upper
bound reduces to a similar extremal problem for abelian groups using some
ideas of \cite{GLP}, \cite{LP} and the following Theorem which is the
main new ingredient in \cite{LN}.

Let $X(\mathbb{F}_q)$ be a finite quasisimple group of Lie type
$X$ over the finite field $\mathbb{F}_q$ of characteristic $p>3$.
For a subgroup $H$ of $X(\mathbb{F}_q)$ define
\[ t(H)=\frac{ \log[X(\mathbb{F}_q):H]}{\log|H^{\diamondsuit}|},\]
 where $H^{\diamondsuit}$ denotes the maximal abelian
 quotient of $H$ whose order is coprime to $p$. Set $t(H)=\infty$ if $|H^{\diamondsuit}|=1$.
\medskip

Recall that $R=R(X)=h/2$ where $h$ is the Coxeter number of the root system of the \textbf{split} Lie type corresponding to $X$.

\begin{theorem}\label{t4} Given the Lie type $X$ then
\[ \liminf_{q \rightarrow \infty} \ \min \left \{ t(H)\ |\quad H\leq X(\mathbb{F}_q)\ \right \} \geq R.\]
\end{theorem}

The proof of this theorem does not depend on the classification of the finite simple groups, we use
instead the work of Larsen and Pink \cite{lpink} (which is a classification-free version of a result of Weisfeiler \cite{We}), and Liebeck, Saxl
and Seitz \cite{lss} (the latter for groups of exceptional type).

\textbf{Part II:}

Once Part I is proved, the argument reduces to an extremal problem on abelian groups:
\begin{theorem}\label{ab} Let $d$ and $R$ be fixed positive numbers. Suppose $A=C_{x_1}\times C_{x_2}\times \cdots \times C_{x_t}$ is an abelian group such that the orders $x_1,x_2,...,x_t$ of its cyclic factors do not repeat more than $d$ times each. Suppose that $r|A|^R\leq n$ for some positive integers $r$ and $n$. Then as $n,r$ tend to infinity we have
\[s_r(A)\leq n^{(\gamma +o(1))\frac{\log n}{\log \log n}},\]
where $\gamma=\frac{ (\sqrt{R(R+1)}-R)^2}{4R^2}$.
\end{theorem}

The starting point of the proof of this theorem in \cite{GLP} is a well-known formula for counting subgroups of finite abelian groups (see \cite{Bu}). We refer the reader to \cite{GLP} for the details which are too complicated to be given here.

\subsection*{Acknowledgments} In their work the authors were supported by
grants from the National Science Foundation (Goldfeld and Lubotzky), the Israel Science Foundation and the US-Israel Binational Science Foundation (Lubotzky) and Hungarian National Foundation for Scientific Research, Grant T037846 (Pyber). While this research was carried out Nikolov held a
Golda-Meir Postdoctoral Fellowship at the Hebrew University of
Jerusalem.

config: arxiv


TITLE: An integral formula for the multiplication of inverses.
QUESTION [2 upvotes]: I've tried to find a similar formula of following.
I've heard about this formula
\begin{align}
  \prod_{i=1}^n \dfrac{1}{a_i} = \Gamma(n)\left[ \prod_{i=1}^n \int_0^1 \mathrm{d }x_i\right]\dfrac{\delta(1-\sum_{i=1}^n x_i)}{(\sum_{i=1}^n a_i x_i)^n}
\end{align} in a class. ($\delta(x)$ is a Dirac-delta function. I use this for convenience.)
I checked that it's okay when $n=2$.
I tried to prove this but I've noticed when $n=3$, it holds that
\begin{align}
 \int_0^1 \int_0^1 \mathrm{d}x_1 \mathrm{d}x_2 \dfrac{1}{(m_1 x_1 + m_2 x_2 + m_3)^3} &= \int_0^1 \int_{m_1 x_1 + m_3}^{m_1 x_1 + m_2 + m_3} \dfrac{\mathrm{d}x_1 \mathrm{d} u}{m_2 u^3}\\
&= -\dfrac{1}{2m_2}\int_{0}^1 \dfrac{\mathrm{d}x_1}{(m_1 x_1 + m_2 + m_3)^2} - \dfrac{\mathrm{d}x_1}{(m_1 x_1 + m_3)^2}
\\
&=\dfrac{1}{2}\dfrac{m_1 + m_2 + 2 m_3}{m_3 (m_1 + m_3)(m_2 + m_3)(m_1 + m_2 + m_3)}\\
\end{align} Obviously, it doesn't coincide with what I want to show.(When substitute $m_1$ to $a-c$, $m_2$ to $b-c$ and $m_3$ to $c$.)
Therefore, I think the formula suggested in the class is wrong. However, it seems to be used in several calculation and so, I think there is a similar formula rather than this.
Could someone tell me what it might be?

REPLY [1 votes]: The formula you cite is correct; in fact, it can be generalized. Your error is assuming $x_2$ integrates from $0$ to $1$; it should be $0$ to $1-x_1$. So the correct result for$$a:=a_1,\,b:=a_2,\,c:=a_3,\,m_1:=a-c,\,m_2:=b-c,\,m_3:=c$$is$$\int_0^1dx_1\int_{m_1x_1+m_3}^{m_1x_1+m_2(1-x_1)+m_3}\frac{du}{m_2u^3}\\=\frac{1}{2m_2}\int_0^1dx_1\left(\frac{1}{(m_1x_1+m_3)^2}-\frac{1}{((m_1-m_2)x_1+m_2+m_3)^2}\right)\\=\frac{1}{2m_2}\left(\frac{1}{m_3(m_1+m_3)}-\frac{1}{(m_1+m_3)(m_2+m_3)}\right)\\=\frac{1}{2(m_1+m_3)m_3(m_2+m_3)}=\frac{1}{2acb}.$$


TITLE: A language that is not even context-sensitive?
QUESTION [3 upvotes]: Is there a language actually in use that can't be recognized by a linear bounded automaton?  I only know of ones that don't have a practical use, like "the set of pairs of equivalent regular expressions with exponentiation" (Wikipedia).  Or would any such language be too slow to recognize to be useful?

REPLY [0 votes]: I think any problem with non-elementary complexity should do, e.g. "correctly typed programs" for some complex type theories might be just an example you look for ;-)


TITLE: If $P$ is a projection matrix such that $PX = X$ does it mean $X$ has a singular distribution?
QUESTION [0 upvotes]: Suppose ${\bf X}$ is a $n \times 1$ vector of random variables and ${\bf P}$ is $n \times n$ a projection matrix such that ${\bf PX} = {\bf X}$. Rank(${\bf P}) < n$. So does it mean that ${\bf X}$ has a singular distribution, for example singular multivariate normal distribution?

REPLY [1 votes]: Since $P$ is not full-rank, its range is a vector subspace of dimension less than n. Every vector subspace of dimension less than n has measure Lebesgue measure 0.
You say that every point in the support of the random variable $X$ is mapped by $P$ to itself. Thus, the support of the random variable $X$ is a subset of $\operatorname{ran}(P)$, which is a vector subspace of dimension less than n. Therefore, the support of $X$ has measure 0. Therefore, $X$ is a singular distribution.


text:
\begin{document}
\title{Fast algebraic immunity of Boolean functions and LCD codes}
\titlerunning{Fast algebraic immunity of Boolean functions and LCD codes}

\author{Sihem Mesnager \inst{1}
\and Chunming Tang \inst{2}
}

\authorrunning{S. Mesnager and C. Tang}

\institute{Department of Mathematics, University of Paris VIII, 93526 Saint-Denis, University Sorbonne Paris Cit\'e, Laboratory Analysis, Geometry and Applications (LAGA), UMR 7539, CNRS, 93430 Villetaneuse,  and Telecom Paris, 91120 Palaiseau, France\\
\email{smesnager@univ-paris8.fr}\\
\and
School of Mathematics and Information, China West Normal University\\
 Nanchong, Sichuan,  637002, China\\
\email{tangchunmingmath@163.com}}

\maketitle

\begin{abstract}
Nowadays, the resistance against algebraic attacks and fast algebraic
attacks are considered as an important cryptographic property for
Boolean functions used in stream ciphers. Both attacks are very
powerful analysis concepts and can be applied to symmetric
cryptographic algorithms used in stream ciphers.
The notion of algebraic immunity has received wide attention since
it is a powerful tool to measure the resistance of a Boolean function
to standard algebraic attacks. Nevertheless, an algebraic tool to
handle the resistance to fast algebraic attacks is not clearly
identified in the literature. In the current paper, we propose a new
parameter to measure the resistance of a Boolean function to fast
algebraic attack. We also introduce the notion of fast immunity profile and
show that it informs both on the resistance to standard and fast
algebraic attacks. Further, we evaluate our parameter for two
secondary constructions of Boolean functions.
Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented.
Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions.
The binary LCD codes presented in this paper have applications in armoring implementations against
 so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems.

  \end{abstract}

{\bf Keywords} Boolean function $\cdot$ (Fast) Algebraic immunity $\cdot$ Algebraic attack  $\cdot$ Fast algebraic attack  $\cdot$ Reed-Muller code $\cdot$ LCD code $\cdot$ Side-channel attack $\cdot$ Fault injection attack.

\section{Introduction}
Boolean functions have important applications in the combiner model and the filter model of stream ciphers. A function used in such an application should mainly possess balancedness, a high algebraic degree, a high nonlinearity and, in the case of the combiner model, a high correlation immunity. In 2003, new kinds of attacks drawn from an original idea of
Shannon \cite{Shannon1949}  emerged; these attacks are called
\emph{algebraic attacks} and \emph{fast algebraic attacks}
\cite{Courtois2003,CourtoisMeier2003,MeierPasalicCarlet2004}.  Since 2003, the designers of cryptosystems in symmetric cryptography need also to ensure resistance to the algebraic attack (they need in practice optimal or almost optimal algebraic immunity) and good resistance to fast algebraic attacks and to the R{\o}njom-Helleseth attack \cite{RH2007,RH2011}, and its improvements.  A first nice primary construction of an infinite class of functions satisfying all the cryptographic criteria (balancedness, the algebraic degree the algebraic immunity and the non-linearity)  is the so-called Carlet-Feng construction \cite{CarletFeng2008}. Note that its good resistance to fast algebraic attacks has first been checked by computer for $n\leq 12$, using an algorithm from \cite{ACGKMR2006}, and later shown mathematically in \cite{Liu2012} for all n. Later, classes of functions have been proposed in the literature in which the authors suggested some modifications of the Carlet-Feng functions and other constructions (see for instance \cite{Carlet2013,CarletTang2015} and the references therein).

(Fast-) algebraic attacks have changed the situation in symmetric cryptography for the steam ciphers by
adding a new criterion of considerable importance to the above list. They
proceed by modeling the problem of recovering the secret key through an over-defined system of multivariate nonlinear equations of
algebraic degree at most $\deg(f)$. The core of algebraic attacks is
to find out low degree Boolean functions $g\not=0$ and $h$ such that
$fg=h$. It is shown in \cite{MeierPasalicCarlet2004} that this is
equivalent to the existence of low algebraic degree \emph{annihilators} of $f$,
that is, of $n$-variable Boolean functions $g$ such that
$f\cdot g = 0$ or $(1+ f)\cdot g=0$. The minimum degree of such $g$ is
called the \emph{algebraic immunity} of $f$, and we denote it by
$\AI(f)$. It must be as high as possible (the optimum value of
$\AI(f)$ being equal to $\left\lceil\frac{n}{2}\right\rceil$).
In 2020, a  novel application of Boolean functions with high algebraic immunity in minimal codes has been derived in \cite{CDMT2020}.
Fast algebraic attacks proceed differently and exploit the existence
of function $g$ of small degree such that the degree of $f\cdot g$ is
not too large. Many authors have indicated that having a high
algebraic immunity is not only a necessary condition for resistance to
standard algebraic attacks but also for resistance to fast algebraic
attacks. Nevertheless, having a high algebraic immunity may not be
sufficient in the design of pseudo-random generators using a Boolean function as filter or combiner
 (see \cite{Carlet2010}).  That motivates to define a new parameter to measure
the resistance of the Boolean function $f$ used in such generators to fast
algebraic attacks. Such a parameter has been proposed in
\cite{CarletTang2015,DuZhangLiu2012,589507}.
Very recently, M\'eaux has studied in \cite{Meaux_FAI_Maj,Meaux_FAI_Thres} the fast algebraic immunity of interesting families of cryptographic Boolean functions, namely the so-called majority functions (which have been intensively studied in the area of cryptography, because of their practical advantages and good properties), and Threshold functions (which are a sub-family of symmetric Boolean functions, which means that the output is independent of the order of the input binary variables). In 2020, Tang \cite{Tang2020} has derived a relation on the fast algebraic immunity between a Boolean function and its modifications, by introducing a new concept called partial fast algebraic immunity. As applications of this relation, he derived some upper bounds on the fast algebraic immunity of several known classes of modified majority functions with optimal algebraic immunity. These bounds show that these modified majority functions still have low fast algebraic immunity, which is coincident with the relation. A very nice reference on this topic is the excellent book of Carlet \cite{Book-Carlet} (which will appear soon).

In this paper, we provide for the first time a link between fast algebraic immune Boolean functions and the so-called \emph{linear complementary dual  code} (abbreviated LCD). An LCD code  is defined as a linear code $\mathcal C$ whose (Euclidean) dual code $\mathcal C ^ \perp$ satisfies $\mathcal C \cap \mathcal C^ \perp=\{\mathbf{0}\}$. LCD codes have been widely applied in data storage, communications systems, consumer electronics, and cryptography. In \cite{mas92}, Massey showed that LCD codes provide an optimum linear coding solution for the two-user binary adder channel. In 2014, Carlet and Guilley  \cite{CG14} investigated an interesting application of binary LCD codes against side-channel attacks (SCA) and fault injection attacks (FIA) and presented several constructions of LCD codes. It was shown non-binary LCD codes in characteristic $2$ can be transformed into binary LCD codes by expansion.  It is then important to keep in mind that, for SCA, the most interesting case is when the code is defined over an alphabet of size $q$ with $q$ even. The recent literature is abundant about LCD codes. One of the most important results on the classification of LCD codes is that any linear code over $\mathbb F_{q}$ ($q>3$) is equivalent to an (Euclidean) LCD code \cite{CMTQP2018}. A complete state-of-the-art on LCD codes can be found in the recent article \cite{CLM2019} and the references therein.

 This paper is organized as follows. In Subsection
\ref{sec:new-definition-fast}, we modify the parameter proposed in
\cite{DuZhangLiu2012,589507} so that it does not depend on the
algebraic immunity as in \cite{DuZhangLiu2012,589507} that we denote
by $\FAI (f)$. We show that the value of the modified parameter is less or
equal to the one proposed in \cite{DuZhangLiu2012} and \cite{589507} for every
Boolean function.
In Subsection \ref{sec:fast-immun-prof}, we introduce the notion of
the immunity profile of a Boolean function and show that both the
algebraic immunity and the $\FAI$ of a Boolean function can be deduced
from this immunity profile.
In Subsection \ref{sec:fast-immun-algebr}, we show that if a function is at low Hamming distance from a low algebraic degree function, then it is weak against fast algebraic attacks and we study further the behavior of $\FAI$.
In Subsection \ref{sec:fast-algebr-immun}, we study
the $\FAI$ of a classical secondary construction of Boolean function,
which it called concatenation Boolean function. We prove that the
$\FAI$ of the concatenation of the Boolean function can be bounded from
below and above by the $\FAI$ of its sub-functions.
Finally, in Section \ref{sec:FAI-LCD} we present a
coding-theory characterization of perfect algebraic immune Boolean functions
by means of the LCD-ness of punctured Reed-Muller codes and derive some new infinite families of LCD codes.

\section{Preliminaries and notation}\label{preliminaries}
In this section, we give a brief introduction to algebraic immunity,
 Reed-Muller codes and linear complementary dual codes, which
are the foundations of other sections.
\subsection{Algebraic immunity of Boolean functions}
Let $n$ be any positive integer. In this paper, we shall denote by
$\B_n$ the set of all $n$-variable Boolean functions over $\F^n$.
Any $n$-variable Boolean function $f$ (that is a mapping from
$\F^n$ to $\F$) admits a unique \emph{algebraic normal form} (ANF),
that is, a representation as a multivariate polynomial over $\F$
\begin{displaymath}
f(x_1,\ldots,x_n)=\sum_{I\subseteq \{1,\ldots ,n\}}
a_I\,\prod_{i\in I}{x_i},
\end{displaymath}
where the $a_I$'s are in $\F$. The terms $\prod_{i\in I} {x_i}$ are
called {\em monomials}.  The {\em algebraic degree} $\deg(f)$ of a
Boolean function $f$ equals the maximum degree of those monomials
whose coefficients are nonzero in its algebraic normal form.

If we identify $\F^n$ with the Galois field $\GF n$  of order
$2^n$, Boolean functions of $n$-variables are then the binary functions over the Galois field $\GF n$ (one can always endow this
vector space with the structure of a field, thanks to the choice of a basis of $\GF n$ over $\F$)
 of order
$2^n$.
The \emph{support} of $f$, denoted by $supp(f)$, is the set of elements of $\GF{n}$ whose image under $f$ is $1$, that is,
$supp(f)=\left \{  x\in \GF{n}: f(x)=1 \right \}$.
The {\em weight} of $f$, denoted by $\wt(f)$, is the {\em
Hamming weight} of the image vector of $f$, that is, the cardinality
of its support $supp(f):=\{x\in \GF{n}\mid f(x)=1\}$.

For any positive integer $k$, and $r$ dividing $k$,
the trace function from $\GF{k}$ to $\GF{r}$, denoted by
$\tr[r]{k}$, is the mapping defined as: $\forall x\in\GF{k} ,\quad
  \tr[r]{k}(x):=\sum_{i=0}^{\frac kr-1}
  x^{2^{ir}}$. In particular, we denote the {\em absolute trace} over $\GF{}$ of an element $x \in
\GF {n}$ by $\tr{n}(x) = \sum_{i=0}^{n-1} x^{2^i}$.
Every non-zero Boolean function $f$ defined on $\GF{n}$ has a (unique)
trace expansion of the form:
\begin{displaymath}
  \forall x\in\GF n ,\quad
  f(x)=\sum_{j\in\Gamma_n}\tr{{o(j)}}(a_jx^{j}) + \epsilon
  (1+x^{2^n-1})
\end{displaymath}
called its polynomial form, where $\Gamma_n$ is the set of integers
obtained by choosing one element in each cyclotomic class of $2$
modulo $2^n-1$, $o(j)$ is the size of the cyclotomic coset of $2$
modulo $2^n-1$ containing $j$, $a_j \in \GF{o(j)}$ and,
$\epsilon=\wt(f)$ modulo $2$.  The algebraic degree of $f$ is equal to
the maximum 2-weight of an exponent $j$ for which $a_j\not= 0$ if
$\epsilon=0$ and to $n$ if $\epsilon=1$. We recall that the $2$-weight
of an exponent $j$, that we denote by $w_2(j)$, is the number of
$1$ in its binary expansion.

An $n$-variable Boolean function $g$ is said to be an {\it
  annihilator} of an $n$-variable Boolean function $f$ if
$f\cdot g=0$, where $f \cdot g$ is the Boolean function whose output equals the product in $\F$ of the outputs of $f$ and $g$. The set of all non-zero annihilators of a Boolean
function $f$ shall be denoted by $\AN(f)$. We shall denote by $\AN^c(f)$
the complement of the set $\AN(f)$, that is, the set of $n$-variable
Boolean function $f$ such that $f\cdot g\not=0$. We shall denote by
$\LDA(f)$ the minimum degree of non-zero annihilators of $f$
\cite{MeierPasalicCarlet2004}. The {\it algebraic immunity} $\AI(f)$
of $f$ is the minimum value between $\LDA(f)$ and $\LDA(1+f)$. Obviously, for  a Boolean function $f$, we have $\AI(1+f)=\AI(f)$. In addition, algebraic immunity is invariant under affine transformations. More specifically, if  $f$ is an $n$-variable Boolean function and $A$ is an affine
  automorphism of $\V n$ then, $\AI(f)=\AI(f\circ A)$.

\subsection{Linear codes and Reed-Muller codes}
An $[\ell,k]$ code $\mathcal C$ over the finite field $\mathbb F_q$ is a linear subspace of
$\mathbb F_q^{\ell}$ with dimension $k$. For convenience, we will denote by $\mathrm{dim}_{\mathbb F_q}(\mathcal C)$
the dimension of the code $\mathcal C$. The dual code, denoted by $\mathcal C^{\perp}$, of $\mathcal C$ is a linear
code with dimension $\ell - k$ and is defined by
$$\mathcal C^{\perp}= \left \{ ( w_{i})_{i=1}^{\ell}\in \mathbb F_q^{\ell}:  \begin{array}{l}
  c_1w_1 + \cdots +c_{\ell } w_{\ell } =0\\
  \text{for all } (c_1, \cdots, c_{\ell})\in \mathcal C
  \end{array}
\right \}.$$

Puncturing and shortening  are classical techniques used to obtain codes of length less than $\ell$ from  mother codes having length $\ell$, thus decreasing the length of codes.
These constructions will be useful for understanding fast algebraic immunity.
Given an $[\ell, k]$ code $\mathcal C$, we can puncture it by deleting the same coordinate $i$ in each codeword. The resulting code is denoted by $\mathcal C^{\{i\}}$.
For any set $D$ of coordinates in $\mathcal C$, we use $\mathcal C^{D}$ to denote the code obtained by puncturing $\mathcal C$ in all coordinates in $D$.
Let $\mathcal C (D)$ be the set of codewords which are $\mathbf 0$ on $D$. Then the shortened code of $\mathcal C$ in all coordinates in $D$, denoted by $\mathcal C_{D}$,
is the code obtained by puncturing the coordinates of $\mathcal C(D)$ in $D$. Puncturing a code is equivalent to shortening the dual code, as explained by the following
proposition,  whose proof can be found in \cite[Theorem 1.5.7]{HP03}.
\begin{proposition}\label{prop:punc-shor-dual}
Let $\mathcal C$ be an $[\ell, k]$ code over $\mathbb F_q$ and let $D$ be any set of coordinates of $\mathcal C$. Then
$$\left ( \mathcal C^D \right ) ^{\perp} = \left ( \mathcal C^{\perp} \right )_{D} \text{ and }
 \left ( \mathcal C_D \right ) ^{\perp} = \left ( \mathcal C^{\perp} \right )^{D}.$$
\end{proposition}

Reed-Muller codes first appeared in print in 1954 and remain ``$\cdots$  one of the oldest and best understood families of codes" \cite[p. 370]{MS86}.
As stated in \cite{Book-Carlet}, we use $\mathrm{RM}(d,n)$ to denote the $d$th-order
Reed-Muller code of length $2^n$. Each codeword in $\mathrm{RM}(d,n)$ is defined by evaluating an $n$-variable Boolean function
$h$ of degree at most $d$ at all points in $\mathbb F_2^n$. The Reed-Muller codes $\mathrm{RM}(d,n)$ have been shown to be equivalent to primitive cyclic codes
(codes of length $2^n-1$) with an overall parity check added \cite{KLP68}. Let $\alpha$ be a primitive element of $\mathbb F_{2^n}$.
Let  $P_0=0$ and $P_j=\alpha^{j-1}$, where
$1\le j \le 2^n-1$.
Then $P_0,...,P_{2^n-1}$ is an enumeration of the points of the vector space $\mathbb F_{2^n}$.

Under this enumeration, the Reed-Muller code $\mathrm{RM}(d, n)$ of order $d $ in $n$ variables may be written as
\begin{eqnarray*}
\mathrm{RM}(d, n)=\left \{(f(P_0), \cdots, f(P_{2^n-1})):  f\in \B _n, \mathrm{deg}(f)\le d \right \}.
\end{eqnarray*}

   We summarize the results on the properties of the Reed-Muller codes in the following theorem.
   For the details of proof we refer the reader to \cite{KLP68,MS86}.
   \begin{theorem}\label{thm:RM}
 Let $n$ be any positive integer and let $0\le d \le n$.
 \begin{enumerate}
 \item[(1)] The Reed-Muller code $\mathrm{RM}(d, n)$ is a binary linear code of dimension $\sum_{i=0}^{d} \binom{n}{i}$.
 \item[(2)] The dual code of $\mathrm{RM}(d, n)$ is the code $\mathrm{RM}(n-d-1, n)$.
 \end{enumerate}

   \end{theorem}

\subsection{Linear complementary dual codes and self-orthogonal codes}
The \emph{hull} of a linear code $\mathcal C$ is defined to be $\mathrm{Hull}(\mathcal C) =\mathcal C \cap \mathcal C^{\perp}$.
When $\mathrm{Hull} (\mathcal C)= \mathcal C$,
$\mathcal C$ is
said to be \emph{self-orthogonal}.
In particular, if $\mathrm{Hull}(\mathcal C) =\mathcal C = \mathcal C^{\perp}$,
then $\mathcal C$ is called a self-dual
code.
 The code $\mathcal C$ is called a \emph{linear complementary dual code} (in brief, an \emph{LCD} code) if $\mathrm{Hull}(\mathcal C)$ is the zero space. These codes have been
 extensively studied recently \cite{CMTQ-DCC,CMTQ-SIG,CMTQP2018,JX,LDL17,LLD17,MTQ}.

 For a matrix $G$, $G^T$ denotes the transposed matrix of $G$. The \emph{Gram matrix} of $G$ is defined to be $GG^{T}$.
 The Gram matrix of a generator of a linear code plays an important role in the study of
 the hulls of linear codes  \cite{GJG18,ZLTD}.
\begin{proposition}\label{prop:LCD-Gram}
 Let $\mathcal C$ be an $[\ell, k]$ linear code over $\mathbb F_q$ with generator matrix $G$. Then
 \begin{eqnarray*}
 \mathrm{dim}_{\mathbb F_q} \left ( \mathrm{Hull} (\mathcal C) \right )=k-\mathrm{Rank} \left (GG^{T}\right).
 \end{eqnarray*}

 In particular,  $\mathcal C$ is LCD (resp. self-orthogonal) if and only if
 $GG^T$ is nonsingular  (resp. $GG^T = 0$).
 \end{proposition}

 A vector $\mathbf x=(x_1, x_2, \ldots, x_{\ell})$ in $\mathbb F_2^{\ell}$ is even-like if

$\sum_{i=1}^{\ell}  x_i=0.$

A binary code is said to be \emph{even-like} if it has only even-like codewords.
 The following proposition gives a necessary condition for an even-like code being LCD
\cite{CMTQ-cha}.
\begin{proposition}\label{prop:dim-even}
Let $\mathcal C$ be an even-like binary code with parameters $[\ell, k]$. If $\mathcal C$ is LCD then  $k$ is an even integer.
\end{proposition}

\section{Fast algebraic immunity and fast immunity profile}

\subsection{A new definition of fast algebraic immunity and its consequences}\label{sec:new-definition-fast}
In the literature, different criteria have been proposed to characterize
the immunity of Boolean functions against fast algebraic attacks; some of those characterizations do not define a parameter but
a property that should satisfy a Boolean function to resist to fast
algebraic attacks \cite{Gong2008,Liu2012,Pasalic2008}.

\begin{definition}\label{dfi:immunite_algebrique}
  Let $f$ be an $n$-variable Boolean function.  We call {\it fast
    algebraic immunity} of $f$, denoted by $\FAI(f)$, the smallest
  value taken by $\deg(g)+\deg(f\cdot g)$ when $g\not \equiv 1$ ranges over the set
  $\AN^c(f)$. We say that such a $g$ {\it achieves} $\FAI(f)$.
\end{definition}

\begin{remark}\label{rem:courtois}
  It has been shown in \cite[Theorem 7.2.1]{Courtois2003} that, for
  any $n$-variable Boolean function $f$ and for every positive
  integers $d$ and $e$ such that $d+e\geq n$, there exists $g$ of
  algebraic degree at most $d$ and $h$ of algebraic degree at most $e$
  such that $f\cdot g=h$.  It implies that $\FAI(f)\leq n$.  Now, one
  has $\deg(f\cdot g)\geq \deg(g)$ if $\deg(f\cdot g)+\deg(g)=\FAI(f)$
  (
 indeed, suppose that $\deg(f \cdot g)< \deg(g)$ then $g$ cannot achieve $\deg(f \cdot g) + \deg(g) = \FAI(f)$, because, denoting $h=f\cdot g$, we have $f\cdot h=h$ and then $h\neq 0$ and $\deg(f \cdot h) + \deg(h)<\deg(f \cdot g) + \deg(g)$). Hence, if $g$ achieves
  $\FAI(f)$ then, necessarily, $\deg(g)\leq\frac n2$ since $\deg(g)+\deg(f \cdot g) =\FAI(f)\le n$ and $\deg(g) \le \deg(f \cdot g)$
  implies that $\deg (g) \leq \frac n2$.

\end{remark}

\begin{remark}\label{rem:courtois}
  In \cite{cryptoeprint:2015:435,Liu2012}, the authors proposed
  different criteria that should satisfy a Boolean function to be
  (almost) resistant to fast algebraic attacks. Those criteria are
  very similar.  Indeed, in \cite[Definition
  1]{cryptoeprint:2015:435}, it is defined that an $n$-variable
  Boolean function $f$ would be \emph{almost optimal resistant}
  against fast algebraic attacks if, for $1\leq e < \frac n2$,
  $\deg(f\cdot g)\geq n-e-1$ whenever $\deg(g)\leq e$ and
  $f\cdot g\not=0$. In \cite[Definition 2]{Liu2012}, the authors
  defined \emph{perfect algebraic immune functions} as the $n$-variable
  Boolean function $f$ such that, for every $1\leq e<\frac n2$,
  $\deg(f\cdot g)\geq n-e$ for any $n$-variable Boolean function $g$
  of algebraic degree at most $e$.

  Observe that the \emph{almost optimal resistance} defined in
  \cite{cryptoeprint:2015:435} is equivalent to $\FAI(f)\geq n-1$
  while the \emph{perfect algebraic immune functions} of \cite{Liu2012} are
  those such that $\FAI(f)\geq n$.

\end{remark}

We first derive from the definition of $\FAI$ an upper bound on the
algebraic degree of Boolean function achieving $\FAI$.

\begin{proposition}\label{prop:degre_min}
  Let $n$ be a positive integer.  Let $f$ be an $n$-variable
  function. Let $g$ an $n$-variable function achieving $\FAI(f)$.
  Then $\deg(g)\leq \left \lfloor\frac{\FAI(f)}2 \right \rfloor$ and
  $\deg(f\cdot g)\geq \left \lceil\frac{\FAI(f)}2 \right \rceil$
\end{proposition}
\begin{proof}
  Let $g\in\AN^c(f)$ achieving $\FAI(f)$, that is,
  $\deg(g)+\deg(f.g)=\FAI(f)$. Necessarily $\deg(f\cdot g)\geq\deg(g)$
  (see Remark \ref{rem:courtois}). Hence $2\deg(g)\leq\FAI(f)$, that
  is, $\deg(g)\leq \left \lfloor\frac{\FAI(f)}2 \right \rfloor$. Thus
  $\deg(f\cdot g)=\FAI(f)-\deg(g)\geq
  \FAI(f)- \left \lfloor\frac{\FAI(f)}2 \right \rfloor= \left \lceil\frac{\FAI(f)}2 \right \rceil$.

 \qed
\end{proof}

In \cite{589507}, it has been proposed another definition than ours
for the fast algebraic immunity. Indeed, in \cite{589507}, the authors
give the following definition for the fast algebraic immunity of a
Boolean function:
\begin{equation}\label{AI:589507}
  \begin{split}
    \min\left(2\AI(f),\min_{1\leq\deg(g)<\AI(f)}(\deg(g)+\deg(f\cdot g))\right).
  \end{split}
\end{equation}
\begin{remark}
Using the definition above, an upper bound of fast algebraic immunity of power functions has been established by Mesnager and Cohen \cite{MesnagerCohenAMC2016}. More precisely,  let $f(x)=Tr_1^n(\gamma x^d)$ where $\gamma\in\mathbb{F}_{2 n}$ and $d$ is a
  positive integer. Suppose that
  $\AI(f)\geq\Big\lceil\frac n{\lfloor{\sqrt n}\rfloor}\Big\rceil+1$.
  Then
  $$
  \FAI(f) \leq u\lfloor{\sqrt n}\rfloor+
  2\Big\lceil\frac n{\lfloor{\sqrt n}\rfloor}\Big\rceil - 1
  $$
  where $u$ is the number of runs of $1$ in the binary representation
  of $d$.

\end{remark}
Note that $\AN^c(f)$ contains all $n$-variable Boolean functions $g$
such that $1\leq\deg(g)<\AI(f)$ because any $g$ of algebraic degree
less than $\AI(f)$ cannot be an annihilator of $f$. Hence
\begin{displaymath}
  \min_{1\leq\deg(g)<\AI(f)}\left(\deg(g)+\deg(f\cdot g)\right)\geq\FAI(f).
\end{displaymath}
Furthermore, $\AN^c(f)$ may contain Boolean function of algebraic
degree greater than or equal to $\AI(f)$, that is,
$\{g:\V n\rightarrow\V{}\mid 1\leq\deg(g)<\AI(f)\}$ is strictly
contained in $\AN^c(f)$. However, (\ref{AI:589507}) is less than
$\FAI(f)$ if and only only if $2\AI(f)<\FAI(f)$. We are now going to
show that the $\FAI$ of a Boolean function or its complement is
necessarily less than or equal to (\ref{AI:589507}). To this end, we
first show that the $\FAI$ of a function can be bounded from above and
below with the lowest degree of the non-zero annihilators of its
complement.

\begin{proposition}\label{thm:borne_FAI_grossiere}
  Let $f$ be a non-zero $n$-variable Boolean function. Then
  $$ \LDA(1+f)+1 \leq\FAI(f)\leq 2\LDA(1+f).$$
\end{proposition}

\begin{proof}
  Note that $g\not\in\AN^c(f)$ says only that $f\cdot g\not=0$.
  Hence, $\AN^c(f)$ contains all the non-zero annihilators of $1+f$
  since $f\cdot g=g$ for every $g\in\AN(1+f)$.  Now, if $g$ is an
  non-zero annihilator of $1+f$ then $f \cdot g=g$ proving that
  $\FAI(f)\leq 2\deg(g)$ from which we deduce that
  $\FAI(f)\leq 2\LDA(1+f)$.

  On the other hand, observe that, if $f\cdot g\not=0$, then
  $f\cdot g$ is an non-zero annihilator of $1+f$. Thus
  $\deg(g)+\deg(f\cdot g)\geq  1+\LDA(1+f)$. \qed
\end{proof}

\begin{remark}\label{rem:borne_inf_tendue}
  The lower bound and the upper bound in Proposition \ref{thm:borne_FAI_grossiere}
  are achieved. Indeed, let $f$ be an $n$-variable Boolean function
  whose support strictly contains the support of an affine Boolean
  function $l$. Then $fl=l$ which implies that $\LDA(1+f)=1$ since
  $(1+f)\cdot l=0$. Thus
  $\deg(l)+\deg(f\cdot l)= 2\deg(l)=2=\LDA(1+f)+1=2\LDA(1+f)$.
\end{remark}

Proposition \ref{thm:borne_FAI_grossiere} says that, for any
$n$-variable Boolean function, $\FAI(f)\leq 2\LDA(1+f)$. Thus, if
$\LDA(1+f)>\LDA(f)$, $\FAI(1+f)\leq 2\LDA(f)=2\AI(f)$ while
$\FAI(f)\leq 2\AI(f)=2\LDA(1+f)$ if $\LDA(1+f)\leq\LDA(f)$.
Summarizing:
\begin{corollary}\label{cor:FAI<=2AI}
  Let $f$ be an $n$-variable Boolean function. Then
  \begin{displaymath}
    \min(\FAI(f),\FAI(1+f))\leq 2\AI(f).
  \end{displaymath}
\end{corollary}
Based on this observation, an extension of fast algebraic immunity is
given by Definition \ref{dfi:immunite_algebrique1}.
\begin{definition}\label{dfi:immunite_algebrique1}
  Let $f$ be an $n$-variable Boolean function. The $\FAA$ of $f$ is
  the minimum value between $\FAI(f)$ and $\FAI(1+f)$:
  \begin{displaymath}
    \FAA(f) = \min(\FAI(f),\FAI(1+f)).
  \end{displaymath}
\end{definition}

A direct consequence of Proposition \ref{thm:borne_FAI_grossiere} is
then that the $\FAA$ of an $n$-variable function is less than or equal
to (\ref{AI:589507}). But above, one deduces from Proposition
\ref{thm:borne_FAI_grossiere}.

\begin{proposition}
  Let $f$ be an $n$-variable Boolean function. Then
  \begin{displaymath}
   \min \left (  \LDA(f)+1, \LDA(1+f)+1  \right ) \leq\FAA(f)\leq2\AI(f).
  \end{displaymath}
\end{proposition}

Another property of $\FAI$ is that it is invariant under affine
transformations like the standard algebraic immunity.
\begin{proposition}\label{prop:affine_invariance}
  Let $f$ be an $n$-variable Boolean function and $A$ an automorphism
  of $\V n$. Then $\FAI(f\circ A)=\FAI(f)$.
\end{proposition}
\begin{proof}
  Note that
  $\{\deg(g)+\deg(f\cdot g)\mid g\in\AN^c(f)\}=\{\deg(g\circ
  A)+\deg(f\circ A\cdot g\circ A)\mid g\in\AN^c(f)\}$.
  Observe now, that $f\cdot g\not=0$ if and only if
  $f\circ A\cdot g\circ A \not=0$, that is, $g\in\AN^c(f)$ if and only
  if $g\circ A\not\in\AN^c(f\circ A)$. Thus $\FAI(f)=\FAI(f\circ A)$. \qed
\end{proof}

One can extend Proposition \ref{prop:affine_invariance} to $\FAA$.
\begin{proposition}
  Let $f$ be an $n$-variable Boolean function and $A$ an automorphism
  of $\V n$. Then $\FAA(f\circ A)=\FAA(f)$.
\end{proposition}

\subsection{Fast immunity profile}
\label{sec:fast-immun-prof}

Set $\MUL_k(f)=\{f\cdot g\mid \deg(g)\leq k\}$ and
$\mu_k(f)=\mindeg\MUL_k(f)$, where $\mindeg$ denotes the minimum degree
of the non-zeros elements of the set. Clearly
$(\mu_k(f)_{1\leq k\leq n}$ is a non-increasing sequence of integers. We
shall call it the \emph{fast immunity profile} of $f$.  Note
that
$\MUL_k(f\circ A)=\{f\circ A\cdot g\mid \deg(g\circ A)\leq k\}
=\{f\cdot h\mid \deg(h)\leq k\}\circ A=\MUL_k(f)\circ A$
for every affine automorphism of $\V n$, proving that
\begin{lemma}\label{profil_invariant}
  Let $f$ be an $n$-variable Boolean function and $A$ an automorphism
  of $\V n$. Then $\mu_k(f)=\mu_k(f\circ A)$ for every
  $1\leq k\leq n$.
\end{lemma}

We now show that the algebraic immunity and the fast
algebraic immunity  of $f$ can be expressed by means of the
immunity profile. We first recall the relationship between the annihilators of a function $f$ and the multiples of $f+1$.

\begin{proposition}\label{LDAMUL}
  Let $f$ be an $n$-variable Boolean function. Then

  $$\LDA(f) = \min_{1\leq k\leq n}\mu_k(f+1).$$

  Furthermore, if $k\geq LDA(f)$, $\mu_k(f+1)=\LDA(f)$.
\end{proposition}
\begin{proof}
  For any integer $k$ ranging from $1$ to $n$, we have
  $\mu_k(1+f)=\mindeg\MUL_k(1+f)\geq\LDA(f)$ since every nonzero
  element of $\MUL_k(1+f)$ is a non-zero annihilator of $f$. It follows that
   $\min_{1\leq k\leq n}\mu_k(f+1)\geq \LDA(f)$.

  Conversely, let $g$ be an annihilator of $f$ of algebraic degree
  $\LDA(f)$. Then one has $(1+f)\cdot g=g$ and thus
  $\mu_{\LDA(f)}(1+f)\leq\LDA(f)$ implying that
  $\min_{1\leq k\leq n}\mu_k(f+1)\leq \LDA(f)$.
  Consequently, $\LDA(f) = \min_{1\leq k\leq n}\mu_k(f+1).$

  Furthermore, note that $(\mu_k(1+f))_{1\leq k\leq n}$ is a
  nonincreasing sequence of integers. Hence, since
  $\mu_{\LDA(f)}(1+f)\leq\LDA(f)$, one has necessarily
  $\mu_{k}(1+f)=\LDA(f)$ when $k\geq\LDA(f)$. \qed
\end{proof}

Recalling that
$\AI(f)=\min(\LDA(f),\LDA(1+f))$, we deduce:

\begin{proposition}\label{AIMUL}
  Let $f$ be an $n$-variable Boolean function. Then
  $$\AI(f)=\min(\min_{1\leq k\leq n}\mu_k(f+1),\min_{1\leq k\leq n}\mu_k(f))$$

\end{proposition}

\begin{proposition}\label{FAIMUL}
  Let $f$ be an $n$-variable Boolean function. Then
  $$\FAI(f)=\min_{1 \leq k\leq n}(k+\mu_k(f)).$$
\end{proposition}
\begin{proof}
  Let $1\leq k\leq n$ be arbitrary.  By definition, $\mu_k(f)$ is the
  lowest algebraic degree of all nonzero elements of
  $\MUL_k(f)$. Thus, for $g \not =0$, $\deg(g)=k$, $f\cdot g\not=0$,
  one has $\deg(f\cdot g)+\deg(g)\geq\mu_k(f)+k$.  Hence, one gets
  that $\FAI(f)\geq\min_{1\leq k\leq n}(k+\mu_k(f))$.  Conversely, let
  $1\leq j\leq n$ be such that
  $j+\mu_j(f)=\min_{1\leq k\leq n}(k+\mu_k(f))$.  Let $h$ be a
  function with $\deg(h)=j$ achieving $\mu_j(f)$ (such that
  $\mu_j(f)=\deg(f\cdot h)$ and $f\cdot h\not=0$).  Then
  $\deg(h)+\deg(f\cdot h)=j+\mu_j(f)\geq \FAI(f)$. \qed
\end{proof}

\section{Fast algebraic immunity, approximation and concatenation of functions}
\subsection{Fast algebraic immunity and approximation of functions}
\label{sec:fast-immun-algebr}

In \cite{Zhang2006} the algebraic complement of a Boolean function and  its algebraic immunity have been studied.

\begin{definition}
  Given a Boolean function $f$ defined on $\V n$, the algebraic
  complement of $f$, denoted by $f^c$, is the function that contains
  all the monomials that are not in the algebraic normal form of $f$.
\end{definition}

In \cite[Theorem 2]{Zhang2006}, the authors have shown that the
algebraic immunities of a Boolean function and its algebraic
complement are close:
\begin{displaymath}
  \vert AI(f) - \AI(f^c) \vert \leq 1.
\end{displaymath}

Let us denote by $\delta_0$ the indicator of the singleton $\{0\}$. It is well-known and easily checked that the algebraic normal form of $\delta_0$ equals $\sum_{I\subseteq \{1,\ldots ,n\}}
\prod_{i\in I}{x_i}$. The algebraic complement of a function $f$ is then the function $f+\delta_0$. Since the algebraic immunity is invariant under affine transformations, there is no reason to privilege $\delta_0$ rather than any other indicator of a singleton $\delta_a$ (except that the ANF of the algebraic complement is nicely simple). Moreover, functions $f+ \delta_a$, $a\in \V n$, are all functions at Hamming distance 1 from $f$, and it seems natural to consider more generally functions at low Hamming distance from $f$. A nice observation has been made in \cite{JohanssonWang2010}: if a function is at low Hamming distance from a low algebraic degree function, then it is weak against fast algebraic attacks. We show now that if a function is at low Hamming distance from a low algebraic immunity function, then it is weak against (standard) algebraic attacks:

\begin{proposition}let $k$ and $d$ be two positive integers. Let $f$ be any $n$-variable Boolean function such that $AI(f)=k$. Let $\delta$ be any Boolean function such that $w_H(\delta)< \min(2^{n-k},2^{d+1}-1)$. Then: $$|AI(f+\delta)-AI(f)|\leq d.$$
\end{proposition}
\begin{proof}
There exists by hypothesis a nonzero annihilator $g$ of $f$ or of $f+1$ whose algebraic degree is $k$.
Let $a_0$ be any element such that $\delta(a_0)=0$ and $g(a_0)=1$.  Such an element exists because the Hamming weight of $g$ is larger than or equal to $2^{n-k}$.

Write $\mathrm{Supp}(\delta)= \left \{ x \in \mathbb F_2^n: \delta (x)=1 \right \}$ and $w=w_H(\delta)$. Let the points
of $\mathrm{Supp}(\delta)$ be $a_1, \cdots, a_w $.  Let $\pi$ be the linear mapping given by
\begin{eqnarray*}
\begin{array}{rl}
\pi: \mathrm{RM}(d,n) & \longrightarrow \mathbb F_2^{w+1}\\
(h(x))_{x\in \mathbb F_2^n} & \mapsto (h(a_i))_{i=0}^{w}.
\end{array}
\end{eqnarray*}
We next claim that the mapping $\pi$ is surjective.
Suppose the claim was false. Then the image of $\pi$ lies  in a hyperplane of $\mathbb F_2^{w+1}$ and
thus we could find a non-zero vector $(c_{a_i})_{i=0}^{w} \in \mathbb F_2^{w+1}$
such that $c_{a_0} h(a_0) + \cdots c_{a_w} h(a_w)=0$ for any $n$-variable Boolean function $h$ of
degree at most $d$. It follows that the vector $(c_x)_{x\in \mathbb F_2^n}$
defined by $c_x= \left \{ \begin{array}{rr}
 c_{a_i}, & \text{ if } x=a_i\\
 \\
 0, & \text{ otherwise}
 \end{array} \right .
$ belongs to the dual code $\mathrm{RM}(d,n)^{\perp}= \mathrm{RM}(n-d-1,n) $ of $\mathrm{RM}(d,n)$.
Note that the weight of the codeword $(c_x)_{x\in \mathbb F_2^n}$ of $\mathrm{RM}(n-d-1,n) $
is less or equal to $w+1$, which contradicts the facts that the minimum distance of
$\mathrm{RM}(n-d-1,n) $ is at least $2^{d+1}$ and $w+1\le 2^{d+1}-1$. Thus $\pi$ is a surjective mapping.
In particular,  there exists a polynomial $h$ of
degree at most $d$ such that $h(a_0)=1$ and $h(a_i)=0$ for $1\le i \le w$.
We have then $(f+\delta)\cdot gh=0$ or $(f+1+\delta)\cdot gh=0$ and $gh$ is an annihilator of $f+\delta$ or of $f+1+\delta$ and
it is nonzero since $(gh)(a_0)=1$. This implies that $AI(f+\delta)\leq AI(f)+d$ and applying this result to $f+\delta$ instead of $f$ gives $AI(f)\leq AI(f+\delta)+d$, which completes the proof. \qed
\end{proof}

Note that this result and the result from \cite{JohanssonWang2010} mentioned above are complementary of each other since the condition of being at low Hamming distance from a low algebraic immunity function is a weaker assumption than being at low Hamming distance from a function of low algebraic degree, and moreover the weakness against standard algebraic attacks is still worse than the weakness against fast algebraic attacks (because when they apply, algebraic attacks are more efficient than fast algebraic attacks), but the result from \cite{JohanssonWang2010} still applies for functions at low Hamming distance from a function whose algebraic degree is not necessarily low, but is not high either; indeed it says that if $w_H(\delta)<\sum_{i=0}^d {n\choose i}$ and $f$ has algebraic degree $k$ then $FAI(f+\delta)\leq k+2d$.\\

Let us now investigate if $\FAI(f)$ and $\FAI(f^c)$ are close or
not. To this end, we shall need the following Lemma.
\begin{lemma}\label{lem:util_encadrement_FAI_alg_compl}
  Let $f\not=\delta_0$ be an $n$-variable Boolean function. Let $g$
  achieving $\FAI(f)$. Then there exists an $n$-variable affine
  function $l$ vanishing at $0$ such that $f\cdot g\cdot l\not=0$.
\end{lemma}
\begin{proof}
  Suppose that for every $n$-variable affine Boolean function $l$
  vanishing at $0$, $f\cdot g\cdot l=0$. Then, for any
  $1\leq i\leq n$, $f\cdot g\cdot l_i=0$ where
  $l_i(x_1,\dots,x_n)=x_i$, that is, $f\cdot g=(1+l_i)h_i$ for some
  $n$-variable Boolean function $h_i$. Therefore,
  $f\cdot g=\delta_0=\prod_{i=1}^nl_i$.  Now,
  $FAI(f)=\deg(f\cdot g)+\deg(g)=n+\deg(g)\leq n$. Hence, $g=1$
  contradicting $f\not=\delta_0$. \qed
\end{proof}

We begin with showing.

\begin{proposition}
  Let $f$ be an $n$-variable Boolean function. Suppose $f\not=\delta_0$
  and $f^c\not=\delta_0$. Then
  $$\vert\FAI(f^c)-\FAI(f)\vert\leq 2.$$
\end{proposition}
\begin{proof}
  According to Proposition \ref{FAIMUL},
  $\FAI(f)=\min_{1\leq k\leq n}(k+\mu_k(f))$.  Let $k\geq 1$
  achieving $\FAI(f)$: $k+\mu_k(f)=\FAI(f)$.

   Let $g$ achieving $\mu_k(f)$:
  $\deg(f\cdot g)=\mu_k(f)$.

  Now, observe that, for any $n$-variable Boolean function $p$,
  $$
  f^c\cdot p
  =f\cdot p + \delta_0\cdot p =
  \begin{cases}
    f\cdot p & \mbox{if $p(0)=0$}\\
    f\cdot p + \delta_0 & \mbox{ if $p(0)=1$}
  \end{cases}
  $$
  But in all cases, for any $n$-variable affine Boolean function $l$
  vanishing at $0$,  $f\cdot g\cdot l=f^c\cdot g\cdot l$ since
  $\delta_0\cdot l=0$. According to Lemma
  \ref{lem:util_encadrement_FAI_alg_compl}, there exists $l$ such that
  $f\cdot g\cdot l=f^c\cdot g\cdot l\not=0$. Then
  \begin{displaymath}
    \begin{split}
      \FAI(f^c) &\leq\deg(f^c\cdot g\cdot l)+\deg(g\cdot l)\\
      &\leq\deg(f^c\cdot g)+\deg(g) + 2 = \FAI(f)+2.
    \end{split}
  \end{displaymath}
  Now, since the algebraic complement of $f^c$ is $f$ itself.
  One can exchange the role of $f$ and its algebraic complement $f^c$ in the
  above arguments and prove
  \begin{displaymath}
    \FAI(f)\leq\FAI(f^c)+2.
  \end{displaymath}
  \qed
\end{proof}
\begin{remark}
  Following the above proof, if the $n$-Boolean function $g$ achieving
  $\FAI(f)$ vansihes at $0$. Then, one has
  $\FAI(f^c)\leq\deg(f^c\cdot g)+\deg(g)=\deg(f\cdot
  g)+\deg(g)=\FAI(f)$.
  Therefore, if $\FAI(f^c)$ is also achieved by an $n$-variable
  Boolean function vanishing at $0$ then,
  $\FAI(f^c)\geq\FAI(f)$. Therefore, we might have $\FAI(f)=\FAI(f^c)$
  for some subclasses of $n$-variable Boolean functions.
\end{remark}
\begin{remark}
  Observe that the condition $f\not=\delta_0$ is not restrictive since
  $\AI(\delta_0)=1$ ($\delta_0\cdot l=0$ if $l(0)=0$ and $\deg(l)=1$).
\end{remark}

\subsection{Fast algebraic immunity and concatenation of Boolean functions}
\label{sec:fast-algebr-immun}

A classical secondary constructions of Boolean functions from Boolean functions in lower dimension
is the following.
\begin{definition}
  Let $f_0$ and  $f_1$ be two $(n-1)$-variable  Boolean functions. The
  concatenation  of  $f_0$  with  $f_1$  is  the  $n$-variable  Boolean
  function defined, for $x=(x_1,\dots,x_n)\in\V n$, by
  \begin{equation}\label{eq:concatenation}
    \begin{split}
    f(x_1,\dots,x_n) &= (x_n+1)f_0(x_1,\dots,x_{n-1})\\
    &\qquad+ x_nf_1(x_1,\dots,x_{n-1})
    \\&=
    \begin{cases}
      f_0(x_1,\dots,x_{n-1}) &\mbox{if $x_n=0$}\\
      f_1(x_1,\dots,x_{n-1}) &\mbox{if $x_n=1$}.
    \end{cases}
  \end{split}
\end{equation}
\end{definition}

Any $n$-variable Boolean function of algebraic degree $k$ can be
written
\begin{equation}\label{eq:g}
  \begin{split}
    g(x_1,\dots,x_n) &=  (x_n+1) g_0(x_1,\dots,x_{n-1}) \\
    &\quad + x_n g_1(x_1,\dots,x_{n-1})
  \end{split}
\end{equation}
where $g_0$ and $g_1$ are $(n-1)$-Boolean function and
\begin{displaymath}
  \deg(g) = \max(\deg(g_0),\deg(g_0+g_1)+1).
\end{displaymath}
Observe that, the product $f\cdot g$, where $f$ is given by
(\ref{eq:concatenation}) and $g$ is given by (\ref{eq:g}), is
\begin{displaymath}
  \begin{split}
    &f(x_1,\dots,x_n)g(x_1,\dots,x_n) \\
    &\quad=  (x_n+1)f_0(x_1,\dots,x_{n-1})g_0(x_1,\dots,x_{n-1}) \\
    &\qquad + x_nf_1(x_1,\dots,x_{n-1})g_1(x_1,\dots,x_{n-1}).
  \end{split}
\end{displaymath}
Hence
\begin{equation}\label{eq:degfg}
  \begin{split}
    &\deg(f\cdot g)+\deg(g)=\max\Big(\deg(f_0g_0)+\deg(g_0),\\
    &\qquad \deg(f_0g_0)+\deg(g_0+g_1)+1,\\
    &\qquad \deg(f_0g_0+f_1g_1)+\deg(g_0)+1,\\
    &\qquad\deg(f_0g_0+f_1g_1)+\deg(g_0+g_1)+2\Big).
  \end{split}
\end{equation}
Based on this observation, we prove
\begin{proposition}\label{prop:concatenation}
  Let $n$ be a positive integer greater than $1$. Let $f_0$ and $f_1$
  be two $(n-1)$-variable Boolean functions. Let $f$ be the
  $n$-variable Boolean function obtained by concatenating $f_0$ with
  $f_1$.  Then
  \begin{displaymath}
    \FAI(f)\geq\min(\FAI(f_0),\FAI(f_1)+1),
  \end{displaymath}
  and
  \begin{displaymath}
    \FAI(f)\leq\min(\FAI(f_0),\FAI(f_1))+2.
  \end{displaymath}
\end{proposition}
\begin{proof}
   Let $g$ an $n$-variable Boolean
  function achieving $\FAI(f)$: $\FAI(f)=\deg(f\cdot g)+\deg(g)$ and
  $f\cdot g\not=0$.  This Boolean function can be written as
  (\ref{eq:g}).  Since $f\cdot g\not=0$, either $f_0\cdot g_0\not=0$
  either $f_1\cdot g_1\not=0$. If $f_0\cdot g_0\not=0$ then, according
  to (\ref{eq:degfg}),
  $\FAI(f)\geq\deg(f_0g_0)+\deg(g_0)\geq\FAI(f_0)$. If $f_0g_0=0$ and
  $f_1g_1\not=0$, then (\ref{eq:degfg}) rewrites as
  \begin{displaymath}
    \begin{split}
      &\deg(f\cdot g)+\deg(g)=\max\Big(
      \deg(f_1g_1)+\deg(g_0)+1,\\
      &\qquad\deg(f_1g_1)+\deg(g_0+g_1)+2\Big).
    \end{split}
  \end{displaymath}
  The result follows then from nothing that
  \begin{itemize}
  \item either $\deg(g_0+g_1)<\deg(g_1)$, wich implies
    $\deg(g_0)=\deg(g_1)$ and thus
    $\FAI(f)\geq \deg(f_1g_1)+\deg(g_0)+1\geq\FAI(f_1)+1$,
  \item either $\deg(g_0+g_1)\geq\deg(g_1)$ which implies that
     $\FAI(f)\geq \deg(f_1g_1)+\deg(g_1)+2\geq\FAI(f_1)+2\geq\FAI(f)+1$.
  \end{itemize}
  Conversely, if we take $g_0$ achieving $\FAI(f_0)$ and $g_1=0$ in
  (\ref{eq:degfg}), then, we get
  \begin{displaymath}
    \FAI(f)\leq \deg(g) = \deg(f_0g_0)+\deg(g_0)+2=\FAI(f_0)+2.
  \end{displaymath}
  Likewise, if we take $g_1$ achieving $\FAI(f_1)$ and $f_0=0$ then,
  \begin{displaymath}
    \FAI(f) \leq \deg(g) = \deg(f_1g_1)+\deg(g_1)+2=\FAI(f_1)+2.
  \end{displaymath}
  \qed
\end{proof}

In \cite{CarletTang2015}, the authors have considered such
construction to design Boolean functions suitable for the filter model
of pseudo-random generator. More precisely, they have considered the particular
case of the concatenation of an $(n-1)$-variable Boolean function $f$
with its complement $1+f$ to $1$. Let us denote $\bar f$ such a concatenation:
\begin{equation}\label{eq:fbar}
  \begin{split}
    \bar f(x_1,\dots,x_n) &= x_n + f(x_1,\cdots,x_{n-1})\\
    &= (x_n+1)f(x_1,\cdots,x_{n-1})\\
    &\quad + x_n (1+f(x_1,\cdots,x_{n-1})).
  \end{split}
\end{equation}
We then deduce from Proposition \ref{prop:concatenation}
\begin{corollary}
  Let $f$ be an $(n-1)$-variable Boolean function. Let $\bar f$ be
  defined by (\ref{eq:fbar}). Then
  \begin{displaymath}
    \min(\FAI(f),\FAI(1+f)+1)\leq\FAI(\bar f)\leq\FAA(f)+2.
  \end{displaymath}
\end{corollary}
Now, note that $1+\bar f$ is the concatenation of $1+f$ with $f$:
\begin{displaymath}
  \begin{split}
    1 + \bar f(x_1,\dots,x_n) &= 1 + x_n + f(x_1,\cdots,x_{n-1})\\
    &= (x_n+1)(1+f(x_1,\cdots,x_{n-1}))\\
    &\quad + x_n f(x_1,\cdots,x_{n-1}).
  \end{split}
\end{displaymath}
Therefore
\begin{corollary}
  Let $f$ be an $(n-1)$-variable Boolean function. Let $\bar f$ be
  defined by (\ref{eq:fbar}). Then
  \begin{displaymath}
    \FAA(f)\leq\FAA(\bar f)\leq\FAA(f)+2.
  \end{displaymath}
\end{corollary}

\section{Fast algebraic immunity and LCD codes}\label{sec:FAI-LCD}
In this section we shall establish the relation between fast algebraic immunity, perfect algebraic immune functions, punctured Reed-Muller codes and binary LCD codes.

The link between the algebraic immunity of Boolean functions and the dimensions of punctured Reed-Muller codes is
described in the following.
\begin{proposition}\label{prop:AI-dim}
 Let $e$ be a positive integer.  Let $f$ be an $n$-variable Boolean function and let $D$ be its support.
 Then the algebraic immunity of $f$ is greater than $e$ if and only if the dimensions of the two punctured Reed-Muller codes
 $\mathrm{RM}(e,n)^{D}$ and $\mathrm{RM}(e,n)^{\overline{D}}$ are both equal to $\mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM(e,n)} \right )$.
\end{proposition}
\begin{proof}
Let $\AI(f)>e$. Assume by way of contradiction,
\begin{eqnarray}\label{eq:dim<dim}
\mathrm{dim}_{\mathbb F_2} \left (\mathrm{RM}(e,n)^{\overline{D}} \right )< \mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM(e,n)} \right ).
\end{eqnarray}
Consider the linear transformation $Res_{D}$ from $\mathrm{RM(e,n)}$ to the punctured code $\mathrm{RM}(e,n)^{\overline{D}}$ defined by
\begin{eqnarray*}
(g(x))_{\mathbb{F}_2^n} \mapsto (g(x))_{x\in D}.
\end{eqnarray*}
By assumption in (\ref{eq:dim<dim}), there exists a nonzero function $g\in \B_n$ of degree at most $e$ such
that $Res_D(g)=(g(x))_{x\in D}=\mathbf{0}$. Then $fg=0$, contrary to $\AI(f)>e$. Hence
$\mathrm{dim}_{\mathbb F_2} \left (\mathrm{RM}(e,n)^{\overline{D}} \right )= \mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM(e,n)} \right ).$
By a similar argument, we can show
 that $\mathrm{dim}_{\mathbb F_2} \left (\mathrm{RM}(e,n)^{{D}} \right )= \mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM(e,n)} \right ).$

As for the converse, suppose the assertion is false. Then we could find a nonzero function $g$ of degree at most $e$
such that $fg=0$ or $(1+f)g=0$. By symmetry, one can assume that $fg=0$. We then have $Res_D(g)=(g(x))_{x\in D}$
is the all zeros codeword of $\mathrm{RM}(e,n)^{\overline{D}}$. We conclude that
the linear transformation $Res_D$  is surjective but not injective. This clearly forces
$\mathrm{dim}_{\mathbb F_2} \left (\mathrm{RM}(e,n)^{\overline{D}} \right )< \mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM(e,n)} \right ),$
a contradiction. Therefore $\AI (f) >e$. \qed
\end{proof}

Given a nonzero Boolean function $f$, let $\left < \mathbf{1}_{\wt (f)} \right >$
denote the binary code generated by the all-ones vector $\mathbf{1}_{\wt (f)}$ of length $\wt (f)$.
To treat fast algebraic immunity of Boolean functions, we need to invoke punctured Reed-Muller codes.
\begin{lemma}\label{lem:deg-dual}
 Let $e, e'$ and $n$ be positive    integers. Let $f$ be an $n$-variable nonzero Boolean function and let $D$ be its support.
 Then the intersection of $\mathrm{RM}(e,n)^{\overline{D}}$ and
 $\left ( \mathrm{RM}(e',n)^{\overline{D}} \right )^{\perp}$
is included in $\left < \mathbf{1}_{\wt (f)} \right >$  if and only if   $\deg (fg) \ge n-e'$ holds
for any $n$-variable nonzero  Boolean function $g\in AN^{c}(f) \setminus \left (1+\AN (f) \right )$
 of degree at most $e$, where $1+\AN (f)=\left \{1+h: h \in \AN (f) \right \}$.
\end{lemma}

\begin{proof}
By Proposition \ref{prop:punc-shor-dual},
\begin{eqnarray*}
\left ( \mathrm{RM}(e',n)^{\overline{D}}  \right )^{\perp} = \left ( \mathrm{RM}(e',n)^{\perp}  \right )_{\overline{D}}.
\end{eqnarray*}
Invoking Part (5) of Theorem \ref{thm:RM}, we get
\begin{eqnarray}\label{eqn:deg-l-h}
\left ( \mathrm{RM}(e',n)^{\overline{D}}  \right )^{\perp} =\mathrm{RM}(n-e'-1,n)  _{\overline{D}}.
\end{eqnarray}

Let us first prove the only if part, so let us suppose that $\mathrm{RM}(e,n)^{\overline{D}}
 \cap \left ( \mathrm{RM}(e',n)^{\overline{D}} \right )^{\perp} \subseteq \left < \mathbf{1}_{\wt (f)} \right > $.
 If there existed a function  $g\in AN^{c}(f) \setminus \left ( 1 +\AN (f)\right )$ such that  $\deg(g)\le e$ and $\deg (fg) \le  n-e'-1$,
 we would have
 \begin{eqnarray*}
 (g(x))_{x \in D} \in \mathrm{RM}(e,n)^{\overline{D}}
 \end{eqnarray*}
 and
 \begin{eqnarray*}
 (g(x)f(x))_{x\in D} \in \mathrm{RM}(n-e'-1,n)_{\overline{D}}.
 \end{eqnarray*}
Then, taking $g\in AN^{c}(f)$ and $supp(f)=D$  into account, one
sees that the nonzero codeword $(g(x))_{x \in D}$ is not equal to $\mathbf{1}_{\wt (f)}$ and lies in the intersection of the punctured code
$\mathrm{RM}(e,n)^{\overline{D}}$ and the shortened code $\mathrm{RM}(n-e'-1,n)_{\overline{D}}$.
From (\ref{eqn:deg-l-h}), we deduce that
$\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e',n)^{\overline{D}}  \right )^{\perp}$
is not included in $\left < \mathbf{1}_{\wt (f)} \right >$, a contradiction.
Hence the proof of the only if part is concluded.

For the converse, suppose the assertion of the lemma is false. Then
we could find a function $g \in AN^{c}(f) $ of degree at most $e$ such that
\begin{eqnarray*}
(g(x))_{x\in D} \in \left ( \mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e',n)^{\overline{D}}  \right )^{\perp} \right ) \setminus \left < \mathbf{1}_{\wt (f)} \right >.
\end{eqnarray*}
Thus, we can apply (\ref{eqn:deg-l-h}) to conclude that $1+g \not \in \AN (f)$ and
$$(g(x)f(x))_{x\in D}=(g(x))_{x\in D}\in \mathrm{RM}(n-e'-1,n)_{\overline{D}}.$$
We thus get $\deg (gf) \le n-e'-1$, a contradiction. This completes the proof. \qed
\end{proof}

\begin{lemma}\label{lem:1-deg-high}
Let $f$ be an $n$-variable nonzero Boolean function and let $D$ be its support. Then
$\mathbf 1_{\wt (f)} \not \in \left ( \mathrm{RM} (e',n)^{\overline{D}} \right )^{\perp}$
if and only if $\deg (f) \ge n-e'$.
\end{lemma}
\begin{proof}
By (\ref{eqn:deg-l-h}), $\mathbf 1_{\wt (f)} \not \in \left ( \mathrm{RM} (e',n)^{\overline{D}} \right )^{\perp}$
if and only if $\mathbf 1_{\wt (f)} \not \in \mathrm{RM} (n-e'-1,n)_{\overline{D}} $.
The desired conclusion then follows from the definition of $\mathrm{RM} (n-e'-1,n)_{\overline{D}}$. \qed
\end{proof}

 The following theorem provides a characterization of fast algebraic immunity of $n$-variable higher degree Boolean functions
 by means of punctured Reed-Muller codes.
\begin{theorem}\label{thm:FAI-s-1-RM}
Let $s$ be a positive integer.  Let $f$ be an $n$-variable nonzero Boolean function with $\deg (f) \ge s-1$
 and let $D$ be its support.
Then the fast algebraic immunity of $f$ is greater than or equal to $s$ if and only if
 $\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e+n-s,n)^{\overline{D}} \right )^{\perp} = \left \{  \mathbf{0} \right \}$
  holds for any $1\le e \le n$.
\end{theorem}
\begin{proof}
Let $f$ be an $n$-variable Boolean function with $\FAI (f) \ge s$.
By the definition of fast algebraic immunity, we have
\begin{eqnarray*}
\deg(g) + \deg(gf) \ge s \text{ for any } g \in \AN^c(f) \setminus \{1\}.
\end{eqnarray*}
Now, as then, we can assert that $\deg (gf) \ge s-\deg (g) \ge n-(e +n-s)$
for any $g\in \AN^c(f)$ with $1\le \deg(g) \le e$.
Therefore $\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e+n-s,n)^{\overline{D}} \right )^{\perp}  \subseteq \left  < \mathbf{1}_{\wt (f)} \right >$
holds for any $1 \le e \le n$
by Lemma \ref{lem:deg-dual}.
As $\deg (f) \ge s-1 \ge n- (e+n-s)$ we have $\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e+n-s,n)^{\overline{D}} \right )^{\perp} =\{\mathbf{0}\} $
from Lemma \ref{lem:1-deg-high}.

Conversely, assume that for any $1 \le e \le n$ one has
$$\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e+n-s,n)^{\overline{D}} \right )^{\perp} =\left \{ \mathbf  0\right \}.$$
Suppose the theorem were false. Then we could find a Boolean function $g \in \AN^c (f) \setminus \{1\}$ such that $\deg(g) + \deg(gf) <s$.
It follows that $\deg(gf) <n-(e+n-s) \le \deg (f)$ and $g(1+f) \not \equiv 0$, where $e=\deg(g)$.
Lemma \ref{lem:deg-dual} now implies that $\mathrm{RM}(e,n)^{\overline{D}} \cap \left ( \mathrm{RM}(e+n-s,n)^{\overline{D}} \right )^{\perp}$
is included in $\left < \mathbf{1}_{\wt (f)} \right >$, a contradiction. This completes the proof. \qed
\end{proof}

The following theorem gives a characterization of perfect algebraic immune
functions using the LCD-ness of the punctured codes of Reed-Muller codes by deleting the coordinates outside the
supports of the Boolean functions.
\begin{theorem}\label{thm:PAI-LCD}
Let $f$ be an $n$-variable nonzero Boolean function and let $D$ be its support.
Then $f$ is a perfect algebraic immune function if and only if
 $\mathrm{RM}(e,n)^{\overline{D}}$ is an LCD code for any $1\le e \le n$.
\end{theorem}
\begin{proof}
Let $f$ be a perfect algebraic immune function.
The perfect algebraic immune function $f$  has degree at least $n-1$ (see \cite{Pasalic2008}).
By Theorem \ref{thm:FAI-s-1-RM} and $\FAI (f) = n$,  $\mathrm{RM}(e,n)^{\overline{D}}$ is  LCD  for any $1\le e \le n$.

Conversely, suppose that $\mathrm{RM}(e,n)^{\overline{D}}$ is an LCD code for any $1\le e \le n$.
The desired conclusion then follows from Theorem \ref{thm:FAI-s-1-RM} and Lemma \ref{lem:1-deg-high}. This completes the proof. \qed
\end{proof}

The following corollary has been proved in \cite{Liu2012} and we give an alternative proof of it based on coding theory.
\begin{corollary}
Let $f$ be an $n$-variable perfect algebraic immune function. Then
$n=2^{\tau}+1$ when $\wt(f)$ is even and $n=2^{\tau}$ when $\wt(f)$ is odd, where $\tau$ is a positive integer.
\end{corollary}
\begin{proof}
Let $f$ be a perfect algebraic immune function and let $D$ be its support.
 Then $\AI (f) \ge n/2$ by Corollary \ref{cor:FAI<=2AI}.
Theorem \ref{thm:PAI-LCD} shows that  $\mathrm{RM}(e,n)^{\overline{D}}$ is an LCD code for any $1\le e \le (n-1)/2$.
Combining Proposition \ref{prop:AI-dim} with Theorem \ref{thm:RM} yields
 $\mathrm{dim}_{\mathbb F_2} \left ( \mathrm{RM}(e,n)^{\overline{D}} \right ) = \sum_{i=0}^{e} \binom{n}{i}$.
 Since $\mathbf{1}_{\wt (f)}$ lies in $\mathrm{RM}(e,n)^{\overline{D}}$,
 $\left ( \mathrm{RM}(e,n)^{\overline{D}} \right )^{\perp}$
 is an even-like LCD code with dimension $\wt (f) - \sum_{i=0}^{e} \binom{n}{i}$.
 We conclude from Proposition \ref{prop:dim-even} that $\wt (f) \equiv  \sum_{i=0}^{e} \binom{n}{i} \pmod{2}$ for any $1\le e \le (n-1)/2$.
 This clearly forces
 \begin{eqnarray}\label{eqn:binom-even}
 n\equiv \wt(f) +1 \pmod{2} \text{ and } \binom{n}{e} \equiv 0 \pmod{2},
 \end{eqnarray}
 where $2\le e \le (n-1)/2$.

Let us first consider the case $\wt (f) \equiv 0 \pmod{2}$. Write $n=2^{\tau}+\sum_{i=0}^{\tau-1} a_i 2^i$.
We have $a_0=1$, because  $n \equiv 1 \pmod{2}$. If there existed an $a_i$ such that $a_i=1$ and $1\le i \le \tau -1$,
we would have $2\le 2^i \le (n-1)/2$ and $\binom{n}{2^i} \equiv 1 \pmod{2}$ by Lucas' Theorem, contrary to (\ref{eqn:binom-even}).
Hence $a_i=0$ and $n=2^{\tau}+1$.

Similar arguments apply to the case $\wt (f) \equiv 1 \pmod{2}$. Then we have $n=2^{\tau}$ in this case.This completes the proof. \qed

\end{proof}

As a corollary of Proposition \ref{prop:AI-dim} and Theorem \ref{thm:PAI-LCD}, we have the following,
which provides a way of constructing LCD codes via perfect algebraic immune function.
\begin{corollary}\label{cor:FAI-LCD}
Let $f$ be an $n$-variable perfect algebraic immune function and let $D$ be its support.
Let $e$ be an integer with $1\le e \le (n-1)/2$.
Then
 $\mathrm{RM}(e,n)^{\overline{D}}$ is an LCD code of dimension $\sum_{i=0}^{e} \binom{n}{i}$.
\end{corollary}

Plugging all the families of perfect algebraic immune functions presented in \cite{CarletFeng2008} and  \cite{Liu2012} into Corollary \ref{cor:FAI-LCD}
 will produce a lot of binary LCD codes.

 \begin{corollary}
 Let $n=2^{\tau}$ or $2^{\tau}+1$. Let $D$ be a subset of $\mathbb F_{2^n}$ given by
 \begin{eqnarray*}
 D= \left \{
 \begin{array}{rl}
 \{\alpha^{\ell}, \alpha^{\ell+1}, \cdots,  \alpha^{\ell+2^{\tau-1}-1} \}, &\text{ if } n=2^{\tau}+1,\\
\\
\{0, \alpha^{\ell}, \alpha^{\ell+1}, \cdots,  \alpha^{\ell+2^{\tau-1}-1} \}, &\text{ if } n=2^{\tau},
 \end{array}
 \right .
 \end{eqnarray*}
 where $\alpha$ is a primitive element of $\mathbb F_{2^n}$ and $\ell$ is an integer.
Then
 $\mathrm{RM}(e,n)^{\overline{D}}$ is an LCD code of dimension $\sum_{i=0}^{e} \binom{n}{i}$ for any $1 \le e \le (n-1)/2$.
 \end{corollary}

\section{Conclusions}

In this paper, we investigated some problems on fast algebraic immunity of Boolean functions and LCD codes. More specifically, we pushed further the general study of the fast algebraic immunity and investigated its behavior in particular for certain families of Boolean functions. We have also introduced the related fast immunity profile and showed that the algebraic immunity and the fast algebraic immunity of a Boolean function can be expressed by means of its immunity profile. In addition, we provided new characterizations of perfect algebraic immune  functions  by means of the LCD-ness of punctured Reed-Muller codes. We also contributed to the current work on binary LCD codes (which are the most important codes regarding its applications in armoring implementations against side-channel attacks and fault non-invasive attacks) by constructing a large class of binary LCD codes from perfect algebraic immune functions. The results show  a novel application of perfect algebraic immune functions in addition to their contribution in symmetric cryptography. This offers a new direction of research in this context.


TITLE: Some questions about finite abelian p-group
QUESTION [0 upvotes]: If $G$ is a finite abelian $p$-group such that $pG=\langle0\rangle$, prove that $G$ is isomorphic to $Z_p+Z_p+...+Z_p$( direct sum of $Z_p$)
I am trying to prove that the order of $G$ is some power of $p$, then the fundamental theorem of finite abelian groups, we will be done.
But how to prove it? And I don't know how to use $pG=\langle 0\rangle$.

REPLY [0 votes]: If $pG = 0$, then we can define a structure of $\mathbb{Z}_{p}$ module over $G$, and so $G$ is a vector space.
Then $$G \cong \mathbb{Z}_{p} \oplus \mathbb{Z}_{p} \ldots \oplus \mathbb{Z}_{p} $$ because this is obvious in the case of vector spaces.


TITLE: Mass of NGC 1097 Galaxy
QUESTION [1 upvotes]: I've been looking all over the internet for this and can't seem to find a reference.  Can anyone refer me to a paper citing the mass of NGC 1097 based on luminosity?

REPLY [1 votes]: You have to distinguish between stellar mass and gravitating mass.
The quoted Milky Way mass includes dark matter.

Despite searching in the literature, I have yet to find reliable apparent magnitudes and good distance estimates for NGC 1097.
The total Blue luminosity of this galaxy is near to Minus B-band absolute magnitude -21, but only ballpark estimates can be made from the existing data. NGC 1097 is significantly more luminous than our own Milky Way Galaxy!
Here is the best that I can do, insofar as estimating the distance and the absolute magnitude and the luminosity of NGC 1097:
http://www.iceinspace.com.au/forum/showthread.php?p=1164458
Unfortunately, NGC 1097 is one of many bright southern galaxies for which there are no "high accuracy"(+/- 10 percent) distance determinations using methods such as TRGB and Cepheids.
People are writing lots of papers on N1097 without having a good idea of how far away it is!!

A more accurate way to estimate the mass, in the form of stars, in a given galaxy, is to base the luminosity estimate of a galaxy on the Near-infrared magnitude, for instance the H or K band magnitude.

Sincerely yours,
Robert
alias madbadgalaxyman


text:
\section{System model}\label{sec:model}
\subsection{Node location and traffic}
We consider a Poisson network: a wireless network consisting of nodes randomly located in a plane according to a Poisson point process (PPP) $\ppp$ on $\R^2$.
The medium access opportunities are arranged into time slots. In each slot, every idle node decides independently from other nodes whether or not to start a new transmission. The duration of this transmission is $\msglen\in\N$ time slots (message length), which is constant for all nodes and over time.
We intend to have on average a fraction $\txp$ of all nodes in $\ppp$ start a new transmission in each slot.
Since only idle nodes start new transmissions, they adopt a sending probability of $\frac{\txp}{1-\txp(\msglen-1)}$.
Let $\txpc$ denote the probability that a node stays idle, i.e., $\txpc=1-\frac{\txp}{1-\txp(\msglen-1)}$ and $S_t$ denote the set of all sending nodes at time $\ti$.
The expected fraction of nodes sending in a given time slot $t$ is thus $\txpd=|S_t|=\txp\,\msglen$, which we refer to as the traffic intensity.

\subsection{Node mobility}
Both static and mobile nodes are investigated.
For mobile nodes, we let $\speed$ denote the average speed of all nodes and consider two mobility models: linear mobility and time-discrete Brownian motion.
The linear mobility model assumes the location of each node $x$ at times $\ti$ and $\ti+\delay$ to change in a random direction with $|x_{\ti}-x_{\ti+\delay}|=\speed\delay$, i.e., the distance increases linearly with time and we set $\mob=\delay$. This can be considered to be a reasonable model for time spans covering the duration of a few time slots, as the direction of movement and speed does not change significantly within the timescale of a slot in a practical system.

The location of a node $x$ with Brownian motion at time $\ti+1$ is~\cite{gong14:tmc,gong11:icc}
\begin{equation}
x_{\ti+1}=x_{\ti}+\speed\mobstep_{\ti}\:,
\end{equation}
where $\mobstep_\ti$ is a two-dimensional Gaussian random variable $\mobstep_\ti\sim N(\vec{0},\Sigma)$ with covariance matrix
\begin{equation}
\Sigma=
\begin{pmatrix}
	0 & \sqrt{\frac{2}{\pi}}\\
	\sqrt{\frac{2}{\pi}} & 0
\end{pmatrix}\:.
\end{equation}
The random variables $\mobstep$ are i.i.d. for each time $\ti$. Hence, the location after $\delay$ slots is
\begin{equation}
\mob=\sum_{\ti=1}^\delay x_t\stackrel{d}{=}\sqrt{\delay}\,\mobstep_0\:,
\end{equation}
where $\stackrel{d}{=}$ denotes the equality in distribution.

\textbf{Remark:} The homogeneity of the PPP describing the node locations is not altered by these two mobility models. At any time $\ti$ the location of nodes forms a PPP with intensity $\dens$. Note that this preservation of homogeneity is not provided by many other mobility models, for example, for the random waypoint model (nodes asymptotically concentrate in the center of the deployment area~\cite{bettstetter03:tmc}).

\subsection{Wireless channel}
The wireless channel is modeled by a distance dependent path loss and multi-path fading accounting for reflections, diffraction, and other small-scale propagation effects.
The signal power at a receiver $x$ from an active sender $y$, with $x,y\in\R^2$ is
\begin{equation}
\rxpwr=\txpwr\,h_\ti^2\,\plossxy\:.
\end{equation}
In this equation, $\txpwr$ is the sending power of $y$, which we consider to be the same for all nodes in the network.
$h_\ti$ models Nakagami-$\nakm$ block fading at time $\ti$ and node $x$, i.e., $h_\ti^2$ is gamma distributed according to $h_\ti^2\sim\Gamma(\nakm,\nakm)$. This implies $\expect{h_\ti^2}=1$ and $\expect{h_\ti^4}=\frac{\nakm+1}{\nakm}
$. The temporal aspect of fading is modeled in the following way~\cite{schilcher12:tmc}:
We consider a block fading model, where the channel is assumed to remain constant over a duration of $\chlen\in\N$ time slots after which it changes to an independent state, i.e., a random experiment is carried out independently of the previous channel state to establish the new channel state. This model for the temporal behavior is of widespread use. It matches well practical systems where the signal timing is usually designed to approximately meet this condition for easing the channel state acquisition and equalization tasks.
Finally, $\plossxy=\ploss{y-x}$ denotes a non-singular distance dependent path loss, for which we adopt
\begin{equation}
\ploss{y-x}=\min(1, \|y-x\|^{-\plc})
\end{equation}
with a path loss exponent $\plc>2$. Let $\plossx=\ploss{x-o}=\ploss{x}$ be the path loss from a node $x$ to the origin $o$.

\subsection{Interference}
Interference at time $\ti$ is measured at the origin $o$ of the plane $\R^2$, which is equal to the interference experienced by a typical node of the network due to Slivnyak's theorem. Its power is the sum of the signal powers of all sending nodes in the network (besides the intended signal from an specific sender, which is not considered in this work) yielding
\begin{equation}
\interf_\ti=\sum_{x\in\ppp}\txpwr\,h_\ti^2\,\plossx\,\gamma_\ti\:,
\end{equation}
where $\gamma_\ti$ is a Bernoulli random variable indicating whether node $x$ is sending ($\gamma_\ti=1$) at time $\ti$ or not ($\gamma_\ti=0$).

\subsection{Classification of correlation sources}\label{ssec:cases}
We consider three sources of correlation of interference: node locations, wireless channel (i.e. correlated fading), and traffic. For each of them, there are three possible options, denoted by a triplet $(i,j,k)\in\{0,1,2\}^3$:
\begin{itemize}
	\item They are constant or the correlation is not considered (denoted by $0$).
	\item They are random but uncorrelated (denoted by $1$).
	\item They are random and correlated (denoted by $2$).
\end{itemize}
This leads to $27$ different cases that have been introduced in more detail and analyzed with respect to temporal correlation of interference in~\cite{schilcher12:tmc}.


TITLE: There exists a nonnull subset $A\in \mathcal{A}$ such that : $ \{f_n\}, \{g_n\}\text{ and }\{h_n\} \text{ are uniformly integrable on }A $?
QUESTION [2 upvotes]: Let $(E,\mathcal{A},\mu)$ be probability space.

Lemma. Suppose $\{f_n\}$ is a sequence  in $\mathcal{L}^1_\mathbb{R}$ such that
$$
\sup_n\int_{E}|f_n|d\mu<+\infty.
$$
Then there exists a nonincreasing sequence $\{B_p\}$ in $\mathcal{A}$ such that $\mu(\cap_p B_p) =0$ and for every $p$
$$
\{f_n\}\text{ is uniformly integrable over }E\setminus B_p
$$

Let $\{f_n\}$, $\{g_n\}$ and $\{h_n\}$ are bounded sequence in $\mathcal{L}^1_\mathbb{R}$. Can we say that there exists a nonnull subset $A\in \mathcal{A}$ such that:
$$
\{f_n\}, \{g_n\}\text{ and }\{h_n\} \text{ are uniformly integrable on }A
$$

REPLY [2 votes]: There are sequences of sets $B_p, B_p', B_p''$ satisfying the conclusion of the lemma for the sequences $\{f_n\}, \{g_n\}, \{h_n\}$ respectively.  Since the intersection of each such sequence has zero measure, continuity from above implies $\mu(B_p) \to 0$ and similarly for $B_p', B_p''$, so given $\epsilon$ we can find $q$ sufficiently large that $\mu(B_q) < \epsilon$, $\mu(B_q') < \epsilon$, $\mu(B_q'') < \epsilon$.  Set $A = (B_q \cup B_q' \cup B_q'')^c$.  By union bound $\mu(A) > 1-3\epsilon$, which is positive as soon as $\epsilon < 1/3$, and by construction all three sequences are uniformly integrable on $A$.


text:
\section{Conclusion}

We presented a \emph{convex} synthesis procedure to design gradient-based algorithms based on a general class of Lur'e Lyapunov functions and linear matrix inequalities. The class of objective functions, which was considered, generalizes the class of strongly convex functions and offers the possibility to incorporate additional information into the algorithm design. It should be emphasized that this class of functions also includes non-convex functions - in particular functions with saddle points. The usefulness of our novel function class was demonstrated, firstly, by showing that additional information about the objective function can boost the convergence rate of algorithms considerably and, secondly, by showing that it can be used to design algorithms for solving optimization problems with linear equality constraints.

Open future research questions are for example the design of distributed algorithms or the design of optimization
algorithms for problems with inequality constraints.


TITLE: Two questions about $p$-groups of class $2$.
QUESTION [1 upvotes]: Let $G$ be a $p$-group of class $2$. Then $G'\subseteq Z(G)$.
Consider following four groups:
$$G', Z(G), G/G', G/Z(G).$$
There is some relations between invariantes of these groups.
(1)  Exponent$(G')=$Exponent$(G/Z(G)$.
(2) Rank$(Z(G))\geq$Rank$(G')$ and Rank$(G/Z(G))\leq$ Rank$(G/G')$.

Q.1. In the second relation, is it true that at least one equality holds?

Considering  (1), it is natural to ask about relation between exponents of  remaining two groups:

Q.2 Is there any relation(equality/inequality) between Exponent$(Z(G))$ and Exponent$(G/G')$?

REPLY [1 votes]: To save typing, I will write $E(G)$ for the exponent of $G$.
For Question 2, $E(G/Z(G)) = E(G')$ and $G' \le Z(G)$ imply $E(G') \le E(G/G')$ and $E(G/Z(G)) \le E(Z(G))$.  Hence
$$E(Z(G)) \le E(G) \le E(G')E(G/G') \le E(G/G')^2$$ and
$$E(G/G') \le E(G) \le E(G/Z(G))E(Z(G)) \le E(Z(G))^2.$$
The examples $$\langle a,b,c \mid a^{p^k} = b^{p^k}=c^{p^{2k}}=1, [a,b]=c^{p^k}, [a,c]=[b,c]=1 \rangle$$ and
$$\langle a,b,c \mid a^{p^{2k}} = b^{p^{2k}}=c^{p^{k}}=1, [a,b]=c, [a,c]=[b,c]=1 \rangle$$
show that both of these bounds are best possible.


TITLE: Why small planets are not attracted by larger planets due to gravitational force?
QUESTION [0 upvotes]: Gravitational force means"the force experienced between two heavenly bodies".A body falls on any planet due to gravitational force.But smaller planets are not attracted by larger planets or stars(sun) due to this force. What is the reason for this?

REPLY [1 votes]: Newton was the first to connect "falling motion" and the motion of "heavenly bodies". He said these two motions had the same origin: the gravitational force. But to explain how the Earth and other heavenly bodies do not fall, while the apple does, he needed to define how motion works and what quantities are involved. In what are now known as Newton's laws (because they seem to hold for all bodies) he said that bodies can and will move in a straight line with constant velocity if no forces are present, and the effect of forces acting simultaneously is such as if only  one force was acting, equal to their sum. Whatever the force, its effect is a change in the motion of the body, possibly in both direction and magnitude. Finally he stated that if a body exerts a force upon another, it will in turn be subjected to an equal and opposite force. These elements, expressed mathematically, allow to describe exactly the motions of the falling apple and the heavenly bodies under their respective conditions.
But to answer your question maybe math is not necessary if we think of similar examples. While a force changes motion, it cannot avoid the inertia of the body, its tendency to "go as it was going". So a force applied sideways to the direction of motion will make it turn (slower or faster depending on how strong the force is compared to how fast the initial motion was). But by the time the turn happens, the body has moved forward a bit. Similarly when turning on a car, the friction of the street on the side of the wheel pushes it sideways, but does not make it turn in place, unless the force is strong enough. In such a way, the Earth is moving away from the Sun  whose force acts sideways to the motion, but it can only make it turn a bit every time the Earth moves forward. Unlike the car, the Earth is moving in a frictionless space and loses almost no energy in its motion, so unlike the car, its forward motion is sustained for extremely long time.

REPLY [0 votes]: As Earth has tangential velocity it will not be pulled into the Sun, but will go into orbit. If it had little or no tangential velocity then it would be pulled into the Sun.


TITLE: Making events disjoint
QUESTION [1 upvotes]: I am reading "A First Course In Probability" by Sheldon Ross, and I am having difficulty solving one of the problems in the book:
For any sequence of events $E_1$, $E_2$, $\ldots\,$,  define a new sequence $F_1$, $F_2$, $\ldots\,$ such that  all the $F_i$ are disjoint and the union from $i=1$ to $n$ of $E_i$ is equal to  the union from $i=1$ to $n$ of $F_i$ for any natural number $n$.

REPLY [3 votes]: Let $$F_i = E_i \setminus \left( \bigcup_{j = 1}^{i-1} E_j \right), $$ i.e. $F_1 = E_1$, $F_2 = E_2 \setminus E_1, F_3 = E_3 \setminus (E_1 \cup E_2), \ldots$


TITLE: Finding the integral for function with floor
QUESTION [2 upvotes]: I am trying to find the integral $$\int_0^n f(x)dx$$
where
$$f(x) = 2ax - {1 \over 2}a^2 - {1 \over 2} a  $$
and
$$ a = \left\lfloor {x \over \phi^2} \right\rfloor $$
and
$$\phi = {1 + \sqrt 5 \over 2}$$
I know how to do a basic integral, but I'm not sure how to handle the floor function.

REPLY [1 votes]: Basically the floor function will make your function look like a step function with many discontinuities. I will assume that $\phi^2|n$.
The thing to do is to notice when the steps happen. That is every $\phi^2$ I believe. Therefore you need to split the region of integration in as many steps you will have for $x\in [0,n]$.
Then integrate each separately. You should notice that at each step, $a$ takes the values $0,1,2,3,...$.
So split the integral, find a general solution for any integer $a$ and then sum the solutions over all possible $a$ constant.
The general case will be: $$\int_{a\phi^2}^{(a+1)\phi^2} 2ax - \frac12a^2 - \frac12a \,dx = \phi^4(2a^2-a) - \frac12\phi^2(a^2+a) = f(a)$$
So the solution is $$\sum_{a=0}^Nf(a)$$
Where $N = \frac{n}{\phi^2}$. Generally, $\phi^2\not|n$ so will will have to add what hasn't been included to the sum.


TITLE: Division of a cubic equation by one of its factors
QUESTION [0 upvotes]: I'm trying to divide a cubic equation by a factor.
This is the equation:
$$ -\lambda^3 -\lambda^2 + 10 \lambda - 8 = 0$$
and this is the factor : $(\lambda - 1)$
I Googled about it and I found the Euclidean division, but I couldn't find some understandable way to do it.

REPLY [2 votes]: Try googling "polynomial long division": You can go directly to this entry in Wikipedia:
Polynomial Long division
Dividing one polynomial by another proceeds just as long division proceeds. And the best way to see how it works is to see some examples (as the linked entry contains), and just try it, do it, practice it.  It won't help you much to provide you with the result: you'll want to see "how" so you can use it here and in any other situation you'll be certain to run across.

REPLY [0 votes]: $$\lambda^3+\lambda^2-10\lambda+8=(\lambda -1)(\lambda^2+2\lambda-8)=(\lambda-1)(\lambda-2)(\lambda+4)$$


TITLE: Why is automated proof checking so hard?
QUESTION [3 upvotes]: (Warn: this is not about automated proving which is impossible. It is about the automatized proof checking).
For example, there is no automated test developed for Wiles Theorem (aka Fermat last theorem) until now.
Why? My naive intuition were that it can't be much harder as the latex-formatted proof in a publication.

REPLY [3 votes]: The short answer is that almost all mathematicians do not write proofs in a sufficiently formalized manner, because they rely on the intelligence of other mathematicians who read their proofs. It is not an issue of unambiguous formatting (type-setting), but an issue of strictly enforced structure and syntax, in much the same way as a compiler will reject a program if there is just one syntax error. Mathematical proofs today are also commonly in prose format, without any indication of scoping, unlike in a typical general-purpose programming language. Also, we see many varieties of 'human' shortcuts like "WLOG" and "It suffices to consider" and "Clearly", which are often not so clear. The amount of mental effort you need to verify a proof yourself with certainty indicates how much information is missing from the proof, which a computer cannot easily supply unlike a person with mathematical training.
One currently ongoing endeavour that may be of interest to you is the Flyspeck Project, which attempts to rectify the lack of absolute confidence in the proof of Kepler's conjecture due to issues such as those mentioned above.


TITLE: Permutation representations of symmetric group of small order
QUESTION [0 upvotes]: Thanks for any comments or help.
What is the list of faithful permutation representations of $S_k$ of degree at most $n=2k$ for $k=3,4,5,6$? Is it possible to find its centralizer in each case?

REPLY [1 votes]: This is easy to do on a computer. For example in magma
http://magma.maths.usyd.edu.au/calc/
The following code:

for k in [3..6] do
X:=Sym(k);
for n in [k..2*k] do
G:=Sym(n);
for sub in Subgroups(G:OrderEqual:=Factorial(k)) do
H:=sub`subgroup;
if IsIsomorphic(H,X) then
[k,n];
Order(Centraliser(G,H));
end if;
end for;
end for;
end for;

will give you all the representations (up to conjugacy in Sym(n)) and the order of the centraliser. It runs in about 10 seconds.
(For example, there are 10 conjugacy classes of Sym(6) in Sym(12), with centralisers of order between 1 and 720.)  If you want more specific information, you can modify the program as needed.


TITLE: "Polynomials" with non-integer exponents
QUESTION [15 upvotes]: Are there some books or articles regarding "polynomials" with non-integer (real) exponents, i.e., $$f(x)=a_1x^{e_1}+a_2x^{e_2}+\dots+a_nx^{e_n},$$
where $e_1,e_2,\dots$ are any real numbers (and $x$ being also real)?
I am mostly interested in theorems regarding the location of the roots, number of the roots, bounds, etc., of such "polynomials". Thanks.

REPLY [7 votes]: I think the keyword is exponential polynomial because $x^\alpha=e^{\alpha \log x}$.
Try these papers:

J.F. Ritt, On the zeros of exponential polynomials,
Trans. Amer. Math. Soc. 31 (1929), 680–686.
C.J. Moreno, The zeros of exponential polynomials (I). Compositio Mathematica, 26 (1973), 69–78.
G.J.O. Jameson, Counting zeros of generalized polynomials: Descartes' rule of signs and Laguerre's extensions,  Math. Gazette 90,(2006), 223–234.