text:
\section{Experiments}
\label{sec:sim}
We evaluate \algname{} on three domains: a set of continuous control tasks, a maze environment that requires exploration, and a dexterous manipulation task.
Throughout these experiments, we use model predictive path integral control (MPPI) \citep{williams2017model} for planning, and
posterior reshaping \citep{chapelle2011empirical} (i.e., scaling of posterior covariance) for Thompson sampling -- we don’t implement \algname{} as analyzed, but rather implement a Thompson sampling variation.
The algorithms are implemented in the Lyceum framework under the Julia programming language \citep{summers2020lyceum,bezanson2017julia}. Comparison algorithms provided by \cite{wang2019exploring,wang2019benchmarking}.
Note that these experiments use reward (negative cost) for evaluations.
Further details of the experiments in this section can be found in Appendix \ref{sec:appsim}.

\subsection{Benchmark Tasks with Random Features}
We use some common benchmark tasks, including MuJoCo \citep{todorov2012mujoco} environments from OpenAI Gym \citep{brockman2016openai}. We use Random Fourier Features (RFF) \citep{rahimi2008random} to represent $\phi$.
Fig. \ref{fig:simpledyn} plots the learning curves against GT-MPPI and the best model-based RL (MBRL) algorithm reported in \cite{wang2019benchmarking}.
It is observed that \algname{} with RFFs quickly increased reward in early stages, indicating low sample complexities empirically.
Table~\ref{tab:finalperf} shows the final performances (at $200$k timesteps) of \algname{} with RFFs for six environments,
and includes its ranking compared to the benchmarks results from \cite{wang2019benchmarking}.
We find that \algname{} consistently performs well on simple continuous control tasks, and it works well even without posterior sampling.
However, when the dynamical complexity increases, such as with the contact-rich Hopper model, our method's performance suffers due to non-adaptation of the RFFs. This suggests that more interesting scenarios require different feature representation.

\begin{figure}[t]
	\begin{center}
		\includegraphics[clip,width=\textwidth]{plot_all.png}
	\end{center}
	\caption{Performance curves of \algname{} with RFFs for different Gym environments.  Note the reward (negative cost) ranges of those plots are made different.  The final mean performances of GT-MPPI and the best model-based RL (MBRL) algorithm reported in \cite{wang2019benchmarking} are also shown for reference.  The algorithm is run for 200,000 timesteps and with four random seeds.  The curves are averaged over the four random seeds and a window size of 5,000 timesteps.}
	\label{fig:simpledyn}
\end{figure}

\begin{table}[t]
	\centering
	\begin{scriptsize}
		\begin{tabular}{lcccccc}
			\toprule
			& InvertedPendulum & Acrobot & CartPole & Mountain Car  & Reacher & Hopper\\
			\midrule
			\algname{} &$-0.0\pm0.0$ & $95.4\pm52.5$ & $199.7\pm0.4$ & $27.3\pm8.1$ & $-4.1\pm1.6$ & $-1016.5\pm607.4$\\

			(Ranking) &$1/11$&$1/11$& $2/11$  & $2/11$ & $1/11$  & $7/11$ \\
			\midrule
			GT-MPPI &$-0.0\pm0.0$ & $177.8\pm25.0$ & $199.8\pm0.1$ & $24.9\pm2.9$ & $-2.4\pm0.1$ & $2995.7\pm215.3$\\
			PETS-CEM& $-20.5\pm28.9$& $12.5\pm29.0$ & $199.5\pm3.0$ & $-57.9\pm3.6$ & $-12.3\pm5.2$ & $1125.0\pm679.6$ \\
			PILCO& $-194.5\pm0.8$& $-394.4\pm1.4$ & $-1.9\pm155.9$ & $-59.0\pm4.6$ & $-13.2\pm5.9$ & $-1729.9\pm1611.1$ \\
			\bottomrule
		\end{tabular}
	\end{scriptsize}
	\caption{Final performances for six Gym environments. Algorithm are run under the same conditions of \cite{wang2019benchmarking}.  The performances of PETS-CEM and PILCO are copied for reference, and the performance of ground-truth MPPI (GT-MPPI) that has access to true model are also shown.  The results are averaged over four random seeds and a window size of 5,000 timesteps.}
	\label{tab:finalperf}
\end{table}

\subsection{Exploring the Maze}
We construct a maze environment to study the exploration capability of \algname{} (see Fig.~\ref{fig:maze} (a)).
State and control take values in $[-1,1]^2\subset\R^2$ and in $[-1,1]\subset\R$, respectively.
The task is to bring an agent to the goal state being guided by
the negative cost (reward) $- c(x_h,u_h) = 8 - \|x_{h}-[1,1]^{\top}\|_2^2$.
We use a one-hot vector of states and actions as features.

We compare the performances, over $50$ episodes with task trajectory length $30$, of \algname{} (with different scale parameters for posterior reshaping) to random walk and PETS-CEM.
Fig.~\ref{fig:maze} (b) plots the means and standard deviations, across four random seeds, of the number of state-action pairs visited over episodes.

We observe that \algname{}'s strategic exploration better modeled the setting for higher rate of success.

\begin{figure}[t]
	\begin{center}
		\includegraphics[clip,width=\textwidth]{plot_maze.png}
	\end{center}
	\caption{Left: An illustration of the maze environment.  Start and End states are $[-1, -1]^{\top}$ and $[1, 1]^{\top}$, respectively.  Dark lines are ``walls''.  Right: The means and standard deviations, across four random seeds, of the number of state-action pairs already explored over episodes.  Covariance scale is the posterior reshaping constant of Thompson sampling.  Random walk takes actions uniformly sampled within $[-1,1]$.  PETS-CEM is a representative model-based RL which uses uncertainty of dynamics but without exploration.  The agent always reaches the goal within $50$ episodes under the best setting of \algname{} and the average number of episodes required for the first success is $25.0$, while random walk and PETS-CEM never bring the agent to the goal within $50$ episodes.}
	\label{fig:maze}
\end{figure}

\subsection{Practical Application}
As we might consider learning model dynamics for the real world in applications such as robotics, we need sufficiently complex features -- without resorting to large scale data collection for feature learning.  One solution to this problem is creating an ensemble of parametric models, such as found in \cite{Tobin17, mordatch2015ensemble}.  We take the perspective that most model parameters of a robotic system will be known, such as kinematic lengths, actuator specifications, and inertial configurations.  Since we would like robots to operate in the wild, some dynamical properties may be unknown: in this case, the manipulated object's dynamical properties.  Said another way, the robot knows about itself, but only a little about the object.

In this experiment, we demonstrate our model learning algorithm on a robotics inspired, dexterous manipulation task.
An arm and hand system (see Fig.~\ref{fig:cooldemo}) must pick up a spherical object with unknown dynamical properties, and hold it at a target position. The entire system has 33 degrees of freedom, and an optimal trajectory would involve numerous discontinuous contacts; the system dynamics are not well captured by random features and such features are not easily learned. We instead use the predictive output of an ensemble of six MuJoCo models as our features $\phi$, each with randomized parameters for the object. Using a single model from the ensemble with the planner is unable to perform the task.

Fig.~\ref{fig:cooldemo} plots the learning curves of \algname{} with different features.  We observe that, within 10 attempts at the task, \algname{} with ensemble features is successful, while the same method with RFF features makes no progress.  Additionally, we use \algname{} with the top layers of a neural network -- trained on a data set of $30$ optimized trajectories with the correct model -- as our features.  It also makes little progress.

We clarify the setting in which this approach may be relevant as follows. Complex dynamics, such as that in the real world, are difficult to represent with function approximation like neural networks or random features.
Rather than collect inordinate amounts of data to mimic the combination of features and model, we instead use structured representations of the real world, such as dynamics simulators, to produce features, and use the method in this work to learn the model.  Since dynamics simulators represent the current distillation of physics into a computational form and accurate measurement of engineered systems is paramount for the modern world, this instantiation of this method is reasonable.

\begin{figure}[t]

	\includegraphics[width=\textwidth]{figures/armhand_and_plot_wide.png}
	\caption{Left: An illustration of Armhand environment.  Right: Performance curves averaged across 12 random seeds.  For reference, we include the average reward of MPPI using a random model from the ensemble. Its score represents the system moving the hand to the object, but unable to grasp and lift it: exactly what we would expect for randomized object dynamics parameters.}
	\label{fig:cooldemo}
\end{figure}

config: arxiv


TITLE: Prove that $\lim_{n \to \infty} \binom{n}{k}a^n = 0$
QUESTION [5 upvotes]: I'm working with this problem but I have no idea how to solve it. Here $k$ is fixed and $0<a<1$.
I was trying to use that $\lim_{n \to \infty} a^n =0$ and that $\binom{n}{k}\leq\frac{n^k}{k!}$ with the $\epsilon$ definition to prove it, my intention was to show that for $N$ large enough $a^N < \frac{k!}{N^k}$ but I got nowhere. I don't know if using the definition is the best aproach.

REPLY [2 votes]: Let $t_n$ be the $n$-th term. Calculation shows that
$$\frac{t_{n+1}}{t_n}=\frac{\binom{n+1}{k}a^{n+1}}{\binom{n}{k}a^n}=\frac{n+1}{n+1-k}a=\left(1+\frac{k}{n+1-k}\right) a.$$
If $n$ is large enough, $\left(1+\frac{k}{n+1}\right)a \lt b$, for some fixed $b\lt 1$. So after a while, each time we increment $n$ by $1$, $t_n$ decreases by a factor of at least $b$.


TITLE: Using Cauchy's Integral Formula on a simple closed contour
QUESTION [2 upvotes]: Hello I'm trying to evaluate the following two integrals where C is the unit circle centered at origin, but I encounter the same problem in both of them and can't think of what to do.
$$1)\ \oint_{C} \frac{1}{(2z-1)^2}$$
for this problem I let $f(z)= \frac{1}{2z-1}$ so I know the integral is equal to $\frac{1}{2}2\pi i f(\frac{1}{2})$ but here is where I have trouble understanding if I evaluate $f(\frac{1}{2})$ it is undefined so how would I go about this? Am I making $f(z)$ the wrong thing? I know the final answer is $0$ just don't understand how to get there.
$$2)\ \oint_{C}e^{z^{2}} (\frac{1}{z^{2}} - \frac{1}{z^{3}}) $$
For this problem I tried dividing this into two integrals and giving each on its $f(z)$ but again the singularity point is at $0$ so I would have to evaluate $f(0)$ for $f(z)=\frac{e^{z^{2}}}{z}$ and $f(z)=\frac{e^{z^{2}}}{z^{2}}$ this has a solution of $-2\pi i$ so again I don't know what do do when $f(z)$ is undefined. Thank you guys in advanced for the help or any kind of hints. I'm trying to master this to pass my final.

REPLY [2 votes]: Cauchy's integral formula only works when the function $f$ is holomorphic inside the contour you are integrating over. However, you can still use the formula here as long as you are careful what you are calling $f$. For the first one, consider Cauchy's Integral formula for the derivative of $f$:
$$ f'(z_0)= \frac{1}{2 \pi i} \int_{C}\frac{f(z)}{(z-z_0)^2}dz$$
We can make the argument of your first integral look like the one above by noting:
$$ \frac{1}{(2z - 1)^2} = \frac{1}{[2(z - 1/2)]^2} = \frac{1/4}{(z - 1/2)^2}$$
So, if we take $f(z)=1/4$, a constant function, then we can use Cauchy's Integral formula because $f(z)=1/4$ is holomorphic everywhere, so in particular it is holomorphic inside the unit disk. The result is:
$$ \int_{C}\frac{1/4}{(z-1/2)^2}dz = 2\pi i*f'(1/2)$$
where again $f(z)=1/4$.
The second integral you present can be done in a similar manner.


TITLE: what is the Jacobian for transformation from complex coordinate to real coordinate?
QUESTION [3 upvotes]: I'm trying to figure out what is the Jacobian when you do this simple transformation:
$dzdz^* \rightarrow dxdy$
where $z=x+iy$ and $z^*=x-iy$.
Follow the formula we have
$$J(x,y)=
\begin{vmatrix}
\frac{\partial z}{\partial x} & \frac{\partial z}{\partial y} \\
\frac{\partial z^*}{\partial x} & \frac{\partial z^*}{\partial y}
\end{vmatrix}
=
\begin{vmatrix}
1 & i \\
1 & -i
\end{vmatrix}=-2i
$$
So $dzdz^* =|J(x,y)| dxdy=2dxdy$. However, this is not what is used in literatures where they either use
$dzdz^* = dxdy$
or
$dzdz^* =2i dxdy$.
So is there a definite answer for this seemingly simple question? Thanks!

REPLY [1 votes]: As differential forms:
\begin{align}
dz \wedge d\bar z &= (dx + i\,dy)\wedge (dx-i\,dy) \\
&= dx \wedge dx - i\, dx\wedge dy + i\,dy \wedge dx + dy \wedge dy \\
&= -2i\,dx \wedge dy
\end{align}


TITLE: For a random permutation, what is the probability the relative order of at least 3 elements are the same?
QUESTION [1 upvotes]: Say there are $K > 3$ distinct numbers $a_1 < a_2 < \dots < a_{K-1}<a_K$. Under a random permutation, what is the probability the relative order of at least 3 elements are the same? Say after the permutation, these elements are labeled as $b_1, b_2, ..., b_K$. The question is what is the probability there exists $i < j < k$ such that $b_i < b_j < b_k$?
PS: Actually, my goal is to prove this probability goes to 1 as K becomes large. I realized the original problem is challenging. If there is an intuitive way to give a lower bound for this probability, it would be great.

REPLY [1 votes]: Certainly the probability goes to $1$ as $K\to\infty$. Here is a way to see this:
Let's say the permutation is of $1, 2, 3, ..., K$.  The probability that $1, 2, 3$ appear in order is $\frac16$; and therefore the probability that they don't occur in order is $\frac56$. The same for the elements $4, 5, 6$. So the probability that both $1,2,3$ and $4, 5, 6$ are out of order is $\left(\frac56\right)^2$. So the probability that either $1,2,3$ or $4,5,6$ is in order is $1-\left(\frac56\right)^2$. In general, the probability that at least one of $1, 2, 3$ or $4, 5, 6$ or ... or $3t-2, 3t-1, 3t$ is in order is $1-\left(\frac56\right)^t$, which goes to $1$ as $t$ gets large.
Of course there are many other ways you could get three elements in order, so this just gives a lower bound on the probability. But this lower bound goes to $1$, and so the probability you want also goes to $1$ (even faster).


text:
\begin{document}
\maketitle

\begin{abstract}
A Steinhaus matrix is a binary square matrix of size $n$ which is symmetric, with diagonal of zeros, and whose upper-triangular coefficients satisfy $a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$ for all $2\leq i<j\leq n$. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices $K_2$ is the only regular Steinhaus graph of odd degree. Using Dymacek's theorem, we prove that if $(a_{i,j})_{1\leq i,j\leq n}$ is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix $(a_{i,j})_{2\leq i,j\leq n-1}$ is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size $n$ whose Steinhaus graphs are regular modulo $4$, i.e. where all vertex degrees are equal modulo $4$, only depend on $\left\lceil \frac{n}{24}\right\rceil$ parameters for all even numbers $n$, and on $\left\lceil \frac{n}{30}\right\rceil$ parameters in the odd case. This result permits us to verify the Dymacek's conjecture up to $1500$ vertices in the odd case.
\end{abstract}

\section{Introduction}

Let $s=(a_1,a_2,\ldots,a_{n-1})$ be a binary sequence of length $n-1\geq1$ with entries $a_{j}$ in $\mathbb{F}_2=\{0,1\}$. The \textit{Steinhaus matrix} associated with $s$ is the square matrix $M(s)=(a_{i,j})$ of size $n$, defined as follows:
\begin{itemize}
\item
$a_{i,i}=0$\quad for all $1\leq i\leq n$,
\item
$a_{1,j}=a_{j-1}$\quad for all $2\leq j\leq n$,
\item
$a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$\quad for all $2\leq i<j\leq n$,
\item
$a_{i,j}=a_{j,i}$\quad for all $1\leq i,j\leq n$.
\end{itemize}
By convention $M(\emptyset)=(0)$ is the Steinhaus matrix of size $n=1$ associated with the empty sequence. For example, the following matrix $M(s)$ in $\mathcal{M}_5(\mathbb{F}_2)$ is the Steinhaus matrix associated with the binary sequence $s=(1,1,0,0)$ of length $4$.
$$
M(s)=\left(
\begin{array}{ccccc}
0 & 1 & 1 & 0 & 0\\
1 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 1 & 1\\
0 & 1 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0
\end{array}
\right)
$$
The set of all Steinhaus matrices of size $n\geq2$ will be denoted by $\mathcal{SM}_n(\mathbb{F}_2)$. It is clear that, for every positive integer $n$, the set $\mathcal{SM}_n(\mathbb{F}_2)$ has a cardinality of $2^{n-1}$.
\par The \textit{Steinhaus triangle} associated with $s$ is the upper-triangular part of the Steinhaus matrix $M(s)$. It was introduced by Hugo Steinhaus in 1963 \cite{Steinhaus1963}, who asked whether there exists a Steinhaus triangle containing as many $0$'s as $1$'s for each admissible size. Solutions of this problem appeared in \cite{Harborth1972,Eliahou2004}. A generalization of this problem to all finite cyclic groups was posed in \cite{Molluzzo1978} and was partially solved in \cite{Chappelon2008}.
\par The \textit{Steinhaus graph} associated with $s$ is the simple graph $G(s)$ on $n$ vertices whose adjacency matrix is the Steinhaus matrix $M(s)$. A vertex of a Steinhaus graph $G(s)$ is usually labelled by its corresponding row number in $M(s)$ and the $i$th vertex of $G(s)$ will be denoted by $V_i$. For instance, the following graph is the Steinhaus graph $G(s)$ associated with the sequence $s=(1,1,0,0)$.
$$
\psmatrix[colsep=0.5cm,rowsep=0.5cm,mnode=circle]
1&&2\\
&3\\
5&&4
\ncline{-}{1,1}{1,3}
\ncline{-}{1,1}{2,2}
\ncline{-}{1,3}{3,3}
\ncline{-}{3,3}{2,2}
\ncline{-}{3,1}{2,2}
\endpsmatrix
$$
For every positive integer $n$, the zero-edge graph on $n$ vertices is the Steinhaus graph associated with the sequence of zeros of length $n-1$.

Steinhaus graphs were introduced by Molluzzo in 1978 \cite{Molluzzo1978}. A general problem on Steinhaus graphs is that of characterizing those satisfying a given graph property. The bipartite Steinhaus graphs were characterized in \cite{Chang1999,Dymacek1986,Dymacek1995} and the planar ones in \cite{Dymacek2000a}. In \cite{Dymacek2000}, the following conjectures were made:

\begin{conj}\label{conj1}
The regular Steinhaus graphs of even degree are the zero-edge graph on $n$ vertices, for all positive integers $n$, and the Steinhaus graph $G(s)$ on $n=3m+1$ vertices generated by the periodic sequence $s=(1,1,0,\ldots,1,1,0)$ of length $3m$, for all positive integers $m$.
\end{conj}

\begin{conj}\label{conj2}
The complete graph on two vertices $K_2$ is the only regular Steinhaus graph of odd degree.
\end{conj}

These conjectures were verified up to $n\leq 25$ in 1988 by exhaustive search \cite{Bailey1988}. More recently \cite{Augier2008}, Augier and Eliahou extended the verification up to $n\leq117$ vertices by considering the weaker notion of \textit{parity-regular} Steinhaus graphs, i.e. Steinhaus graphs where all vertex degrees have the same parity. They searched regular graphs in the set of parity-regular Steinhaus graphs. This has enabled them to perform the verification because it is known that Steinhaus matrices associated with parity-regular Steinhaus graphs on $n$ vertices depend on approximately $n/3$ parameters \cite{Bailey1988,Augier2008}. This result is based on a theorem, due to Dymacek, which states that Steinhaus matrices associated with parity-regular Steinhaus graphs of even type are \textit{doubly-symmetric} matrices, i.e. where all the entries are symmetric with respect to the diagonal and the anti-diagonal of the matrices. A short new proof of this theorem is given in Section $2$. Using Dymacek's theorem, Bailey and Dymacek showed \cite{Bailey1988} that binary sequences associated with regular Steinhaus graphs of odd degree are of the form $(x_1,x_2,\ldots,x_k,x_k,\ldots,x_2,x_1,1)$. In Section $3$, we refine this result and, more precisely, we prove that if $(a_{i,j})_{1\leq i,j\leq n}$ is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree, then its sub-matrix $(a_{i,j})_{2\leq i,j\leq n-1}$ is a \textit{multi-symmetric} Steinhaus matrix, i.e. a doubly-symmetric matrix where each row of the upper-triangular part is a symmetric sequence. A parametrization and a counting of multi-symmetric Steinhaus matrices of size $n$ are also given in Section $3$ for all $n\geq1$. In Section $4$, we show that, for a Steinhaus graph whose Steinhaus matrix is multi-symmetric, the knowledge of the vertex degrees modulo $4$ leads to a system of binary equations on the entries of its Steinhaus matrix. In Section $5$, we study the special case of multi-symmetric Steinhaus matrices whose Steinhaus graphs are \textit{regular modulo $4$}, i.e. where all vertex degrees are equal modulo $4$. We show that a such matrix of size $n$ only depends on $\left\lceil \frac{n}{24}\right\rceil$ parameters for all $n$ even, and on $\left\lceil \frac{n}{30}\right\rceil$ parameters in the odd case. Using these parametrizations, we obtain, by computer search, that for all positive integers $n\leq 1500$, the zero-edge graph on $n$ vertices is the only Steinhaus graph on $n$ vertices with a multi-symmetric matrix and which is regular modulo $4$. This permits us to extend the verification of Conjecture~\ref{conj2} up to $1500$ vertices.

\section{A new proof of Dymacek's theorem}

Recall that a square matrix $M=(a_{i,j})$ of size $n\geq1$ is said to be \textit{doubly-symmetric} if the entries of $M$ are symmetric with respect to the diagonal and to the anti-diagonal of $M$, that is
$$
a_{i,j} = a_{j,i} = a_{n-j+1,n-i+1},\quad \text{for\ all}\ 1\leq i,j\leq n.
$$

In \cite{Dymacek2000}, Dymacek characterized the parity-regular Steinhaus graphs. These results are based on the following theorem on parity-regular Steinhaus graphs of even type, where all vertex degrees are even.

\begin{thm}[Dymacek's theorem]\label{thm6}
The Steinhaus matrix of a parity-regular Steinhaus graph of even type is doubly-symmetric.
\end{thm}

In this section we give a new easier proof of Dymacek's theorem. The main idea of our proof is that the anti-diagonal entries of a Steinhaus matrix are determined by the vertex degrees of its associated Steinhaus graph.

\begin{thm}\label{thm1}
Let $G$ be a Steinhaus graph on $n\geq2$ vertices and $M=(a_{i,j})$ its associated Steinhaus matrix. Then every anti-diagonal entry of $M$ can be expressed by means of the vertex degrees of $G$. If we denote by $\deg(V_i)$ the degree of the vertex $V_i$ in $G$, then for all $1\leq i\leq\left\lfloor \frac{n}{2}\right\rfloor$, we have
$$
a_{i,n-i+1} \equiv \sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{i+k+1}\right)} \equiv \sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{n-i-k}\right)} \pmod{2}.
$$
\end{thm}

The proof is based on the following lemma which shows that each entry of the upper-triangular part of a Steinhaus matrix $M=(a_{i,j})$ can be expressed by means of the entries of the first row $\{a_{1,2} , \ldots , a_{1,n}\}$, the last column $\{a_{1,n} , \ldots , a_{n-1,n}\}$ or the over-diagonal $\{a_{1,2} , \ldots , a_{n-1,n}\}$ of $M$.

\begin{lem}\label{lem1}
Let $M=(a_{i,j})$ be a Steinhaus matrix of size $n\geq2$. Then, for all $1\leq i<j\leq n$, we have
$$
a_{i,j} = \sum_{k=0}^{i-1}{\binom{i-1}{k}a_{1,j-k}} = \sum_{k=0}^{n-j}{\binom{n-j}{k}a_{i+k,n}} = \sum_{k=0}^{j-i-1}{\binom{j-i-1}{k}a_{i+k,i+k+1}}.
$$
\end{lem}

\begin{proof}
Easily follows from the relation: $a_{i,j} = a_{i-1,j-1}+a_{i-1,j}$ for all $2\leq i<j\leq n$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm1}]
We begin by expressing each vertex degree of the Steinhaus graph $G$ by means of the entries of the first row, the last column and the over-diagonal of $M$. Here we view the entries $a_{i,j}$ as $0$,$1$ integers. For all $2\leq i\leq n-1$, we obtain
$$
\deg(V_i)
\begin{array}[t]{l}
= \displaystyle\sum_{j=1}^{n}{a_{i,j}} = \sum_{j=1}^{i-1}{a_{j,i}} + \sum_{j=i+1}^{n}{a_{i,j}}\\
\equiv \displaystyle\sum_{j=1}^{i-1}{(a_{j,i+1}+a_{j+1,i+1})} + \sum_{j=i+1}^{n}{(a_{i-1,j-1}+a_{i-1,j})}\\
\equiv \displaystyle\sum_{j=1}^{i-1}{a_{j,i+1}} + \sum_{j=2}^{i}{a_{j,i+1}} + \sum_{j=i}^{n-1}{a_{i-1,j}} + \sum_{j=i+1}^{n}{a_{i-1,j}}\\
\equiv a_{1,i+1} + a_{i,i+1} + a_{i-1,i} + a_{i-1,n} \pmod{2}.
\end{array}
$$
By Lemma~\ref{lem1}, it follows that
$$
\sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{i+k+1}\right)}
\begin{array}[t]{l}
\equiv \displaystyle\sum_{k=0}^{i-1}{\binom{i-1}{k}(a_{1,i+k+2}+a_{i+k+1,i+k+2}+a_{i+k,i+k+1}+a_{i+k,n})}\\
\equiv \displaystyle\sum_{k=0}^{i-1}{\binom{i-1}{k}a_{1,2i-k+1}} + \sum_{k=0}^{i-1}{\binom{i-1}{k}a_{i+k+1,i+k+2}}\\
+ \displaystyle\sum_{k=0}^{i-1}{\binom{i-1}{k}a_{i+k,i+k+1}} + \sum_{k=0}^{i-1}{\binom{i-1}{k}a_{i+k,n}}\\
\equiv a_{i,2i+1}+a_{i+1,2i+1}+a_{i,2i}+a_{i,n-i+1}\equiv a_{i,n-i+1} \pmod{2},
\end{array}
$$
for all $1\leq i\leq\left\lfloor \frac{n}{2}\right\rfloor$. The second congruence can be treated by the same way.
\end{proof}

\begin{rem}
We deduce from Theorem~\ref{thm1} a necessary condition on the vertex degrees of a given labelled graph to be a Steinhaus graph. Indeed, vertex degrees of a Steinhaus graph on $n$ vertices must satisfy the following binary equations:
$$
\sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{i+k+1}\right)} \equiv \sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{n-i-k}\right)} \pmod{2},\quad \text{for\ all}\ 1\leq i\leq\left\lfloor \frac{n}{2}\right\rfloor.
$$
More generally, an open problem, corresponding to Question $3$ in \cite{Dymacek1996}, is to determine if an arbitrary graph, not necessary labelled, is isomorphic to a Steinhaus graph.
\end{rem}

Now, we characterize doubly-symmetric Steinhaus matrices.

\begin{prop}\label{prop1}
Let $M=(a_{i,j})$ be a Steinhaus matrix of size $n\geq3$. Then the following assertions are equivalent:
\begin{itemize}
\item[(i)]
the matrix $M$ is doubly-symmetric,
\item[(ii)]
the over-diagonal of $M$ is a symmetric sequence,
\item[(iii)]
the entries $a_{i,n-i+1}$ of the anti-diagonal of $M$ vanish for all $1\leq i\leq \left\lfloor \frac{n-1}{2}\right\rfloor$.
\end{itemize}
\end{prop}

\begin{proof}
\ \\[2ex]
$\mathbf{(i)\Longrightarrow(ii):}$ Trivial.\\[2ex]
$\mathbf{(ii)\Longrightarrow(iii):}$ Suppose that the over-diagonal of $M$ is a symmetric sequence, that is
$$
a_{i,i+1} = a_{n-i,n-i+1},
$$
for all $1\leq i\leq n-1$. If $n$ is odd, then we have
$$
a_{i,n-i+1} = \displaystyle\sum_{k=0}^{n-2i}{\binom{n-2i}{k}a_{i+k,i+k+1}} = \displaystyle\sum_{k=0}^{\frac{n-2i+1}{2}}{\binom{n-2i}{k}(a_{i+k,i+k+1}+a_{n-i-k,n-i-k+1})} = 0,
$$
for all $1\leq i\leq\left\lfloor \frac{n-1}{2}\right\rfloor$. Otherwise, if $n$ is even, then we obtain
$$
a_{i,n-i+1} = \displaystyle\sum_{k=0}^{\frac{n}{2}-i-1}{\binom{n-2i}{k}(a_{i+k,i+k+1}+a_{n-i-k,n-i-k+1})} + 2\binom{n-2i-1}{\frac{n}{2}-i}a_{\frac{n}{2},\frac{n}{2}+1} = 0,
$$
for all $1\leq i\leq\left\lfloor \frac{n-1}{2}\right\rfloor$.\\[2ex]
$\mathbf{(iii)\Longrightarrow(i):}$ By induction on $n$. Consider the sub-matrix $N=(a_{i,j})_{2\leq i,j\leq n-1}$ that is a Steinhaus matrix of size $n-2$. By induction hypothesis, the matrix $N$ is doubly-symmetric. Then it remains to prove that $a_{1,j}=a_{n-j+1,n}$ for all $2\leq j\leq n$. First, since $a_{1,n}=0$, it follows that $a_{1,n-1}=a_{1,n}+a_{2,n}=a_{2,n}$ and for all $2\leq j\leq n-2$, we have
$$
a_{1,j} = \sum_{k=j+1}^{n-1}{a_{2,k}} + a_{1,n-1} = \sum_{k=2}^{n-j}{a_{k,n-1}} + a_{2,n} = a_{n-j+1,n}.
$$
\end{proof}

We are now ready to prove Dymacek's theorem.

\begin{proof}[Proof of Theorem~\ref{thm6}]
Let $G$ be a parity-regular Steinhaus graph of even type on $n$ vertices and $M=(a_{i,j})$ its Steinhaus matrix. If $n=1$, then $M=(0)$ which is trivially doubly-symmetric. Otherwise, for $n\geq2$, Theorem~\ref{thm1} implies that
$$
a_{i,n-i+1} \equiv \sum_{k=0}^{i-1}{\binom{i-1}{k}\deg\left(V_{i+k+1}\right)} \equiv 0 \pmod{2},
$$
for all $1\leq i\leq \left\lfloor \frac{n}{2}\right\rfloor$. Finally, the matrix $M$ is doubly-symmetric by Proposition~\ref{prop1}.
\end{proof}

\section{Multi-symmetric Steinhaus matrices}

In this section, we will study in detail the structure of Steinhaus matrices associated with regular Steinhaus graphs of odd degree.

Let $G$ be a Steinhaus graph on $n\geq1$ vertices. Then, for every integer $1\leq i\leq n$, we denote by $G\setminus\{V_i\}$ the graph obtained from $G$ by deleting its $i$th vertex $V_i$ and its incident edges in $G$. Since the adjacency matrix of the graph $G\setminus\{V_1\}$ (resp. $G\setminus\{V_n\}$) is the Steinhaus matrix obtained by removing the first row (resp. the last column) in the adjacency matrix of $G$, it follows that the graph $G\setminus\{V_1\}$ (resp. $G\setminus\{V_n\}$) is a Steinhaus graph on $n-1$ vertices.

Bailey and Dymacek studied the regular Steinhaus graphs of odd degree in \cite{Bailey1988}, where the following theorem is stated, using Dymacek's theorem.

\begin{thm}[\cite{Bailey1988}]\label{thm7}
Let $G$ be a regular Steinhaus graph of odd degree $d$ on $2n\geq4$ vertices. Then $d=n$, the Steinhaus graph $G\setminus\{V_1,V_{2n}\}$ is regular of even degree $n-1$, and $a_{1,j}=a_{1,2n-j+1}$ for all $2\leq j\leq 2n-1$.
\end{thm}

\begin{rem}
In every simple graph, there are an even number of vertices of odd degree. Therefore parity-regular Steinhaus graphs of odd type and thus regular Steinhaus graphs of odd degree have an even number of vertices.
\end{rem}

In their theorem, the authors studied the form of the sequence associated with $G$. We are more interested in the Steinhaus matrix of $G\setminus\{V_1,V_{2n}\}$ in the sequel.

Recall that a square matrix of size $n\geq1$ is said to be \textit{multi-symmetric} if $M$ is doubly-symmetric and each row of the upper-triangular part of $M$ is a symmetric sequence, that is
$$
a_{i,j} = a_{i,n-j+i+1},\quad \text{for\ all}\ 1\leq i<j\leq n.
$$

First, it is easy to see that each column of the upper-triangular part of a multi-symmetric matrix is also a symmetric sequence.

\begin{prop}\label{prop3}
Let $M=(a_{i,j})$ be a multi-symmetric matrix of size $n$. Then, each column of the upper-triangular part of $M$ is a symmetric sequence, that is $a_{i,j} = a_{j-i,j}$ for all $1\leq i<j\leq n$.
\end{prop}

\begin{proof}
Easily follows from the relation: $a_{i,j} = a_{i,n-j+i+1} = a_{j-i,n-i+1} = a_{j-i,j}$ for all $1\leq i<j\leq n$.
\end{proof}

As for doubly-symmetric Steinhaus matrices, multi-symmetric Steinhaus matrices can be characterized as follows.

\begin{prop}\label{prop4}
Let $M=(a_{i,j})$ be a Steinhaus matrix of size $n\geq3$. Then the following assertions are equivalent:
\begin{itemize}
\item[(i)]
the matrix $M$ is multi-symmetric,
\item[(ii)]
the first row, the last column and the over-diagonal of $M$ are symmetric sequences,
\item[(iii)]
the entries $a_{i,n-i+1}$, $a_{n-2i+1,n-i+1}$ and $a_{i,2i}$ vanish for all $1\leq i\leq\left\lfloor\frac{n-1}{2} \right\rfloor$.
\end{itemize}
\end{prop}

\begin{proof}
Similar to the proof of Proposition~\ref{prop1} and by using Lemma~\ref{lem1} and Proposition~\ref{prop3}.
\end{proof}

We now refine Theorem~\ref{thm7}.

\begin{thm}\label{thm5}
Let $G$ be a regular Steinhaus graph of odd degree $n$ on $2n\geq4$ vertices. Then $G\setminus\{V_1,V_{2n}\}$ is a regular Steinhaus graph of even degree $n-1$ whose associated Steinhaus matrix is multi-symmetric.
\end{thm}

\begin{proof}
Let $M=(a_{i,j})$ be the Steinhaus matrix associated with $G$. Theorem~\ref{thm7} implies that the Steinhaus graph $G\setminus\{V_1,V_{2n}\}$ is regular of even degree $n-1$ and that we have
$$
a_{1,j}=a_{1,2n-j+1},
$$
for all $2\leq j\leq 2n-1$. Therefore, for all $3\leq j\leq 2n-1$, we have
$$
a_{2,j} + a_{2,2n-j+2} = (a_{1,j-1} + a_{1,j}) + (a_{1,2n-j+1} + a_{1,2n-j+2}) = (a_{1,j-1} + a_{1,2n-j+2}) + (a_{1,j} + a_{1,2n-j+1}) = 0.
$$
Then the first row of the matrix $B=(a_{i,j})_{2\leq i,j\leq 2n-1}$, the Steinhaus matrix of the graph $G\setminus\{V_1,V_{2n}\}$, is a symmetric sequence. Moreover, by Dymacek's theorem, the matrix $B$ is doubly-symmetric. Finally, by Proposition~\ref{prop4}, the matrix $B$ is multi-symmetric.
\end{proof}

\begin{rem}
By Theorem~\ref{thm5}, it is easy to show that Conjecture~\ref{conj1} implies Conjecture~\ref{conj2}. Indeed, if Conjecture~\ref{conj1} is true, then the zero-edge graph on $n$ vertices is the only regular Steinhaus graph of even degree whose Steinhaus matrix is multi-symmetric. It follows, by Theorem~\ref{thm5}, that if $G(s)$ is a regular Steinhaus graph of odd degree on $n+2$ vertices then $s=(0,\ldots,0,1)$ or $s=(1,\ldots,1)$. Therefore the Steinhaus graph $G(s)$ is the star graph on $n+2$ vertices which is not a regular Steinhaus graph.
\end{rem}

In the sequel of this section we will study in detail the multi-symmetric Steinhaus matrices. First, in order to determine a parametrization of these matrices, we introduce the following operator
$$
T : \mathcal{SM}_n(\mathbb{F}_2) \longrightarrow \mathcal{SM}_{n-3}(\mathbb{F}_2),
$$
which assigns to each matrix $M=(a_{i,j})$ in $\mathcal{SM}_n(\mathbb{F}_2)$ the Steinhaus matrix $T(M)=(b_{i,j})$ in $\mathcal{SM}_{n-3}(\mathbb{F}_2)$ defined by $b_{i,j} = a_{i-1,j-2}$, for all $1\leq i<j\leq n-3$. As depicted in the following matrix, the upper-triangular part of $M$ is an extension of the upper-triangular part of $T(M)$.
$$
\left(
\begin{array}{ccccccccccccc}
0 & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & a_{1,6} & \cdots & \cdots & a_{1,n-4} & a_{1,n-3} & a_{1,n-2} & a_{1,n-1} & a_{1,n}\\
& 0 & a_{2,3} & \mathbf{b_{1,2}} & \mathbf{b_{1,3}} & \mathbf{b_{1,4}} & \cdots & \cdots & \cdots & \mathbf{b_{1,n-5}} & \mathbf{b_{1,n-4}} & \mathbf{b_{1,n-3}} & a_{2,n}\\
& & 0 & a_{3,4} & \mathbf{b_{2,3}} & \mathbf{b_{2,4}} & & & & & \mathbf{b_{2,n-4}} & \mathbf{b_{2,n-3}} & a_{3,n}\\
& & & 0 & a_{4,5} & \mathbf{b_{3,4}} & & & & & & \mathbf{b_{3,n-3}} & a_{4,n}\\
& & & & 0 & a_{5,6} & \ddots & & & & & \vdots & a_{5,n}\\
& & & & & 0 & \ddots & \ddots & & & & \vdots & \vdots\\
& & & & & & \ddots & \ddots & \ddots & & & \vdots & \vdots\\
& & & & & & & 0 & a_{n-5,n-4} & \mathbf{b_{n-6,n-5}} & \mathbf{b_{n-6,n-4}} & \mathbf{b_{n-6,n-3}} & a_{n-5,n}\\
& & & & & & & & 0 & a_{n-4,n-3} & \mathbf{b_{n-5,n-4}} & \mathbf{b_{n-5,n-3}} & a_{n-4,n}\\
& & & & & & & & & 0 & a_{n-3,n-2} & \mathbf{b_{n-4,n-3}} & a_{n-3,n}\\
& & & & & & & & & & 0 & a_{n-2,n-1} & a_{n-2,n}\\
& & & & & & & & & & & 0 & a_{n-1,n}\\
& & & & & & & & & & & & 0
\end{array}
\right)
$$

\begin{prop}\label{prop11}
Let $M=(a_{i,j})$ be a Steinhaus matrix of size $n\geq4$. Then the extension $M$ of $T(M)$ only depends on the parameters $a_{1,2}$, $a_{1,j_0}$ and $a_{1,n}$, with $j_0$ in $\{3,\ldots,n-1\}$.
\end{prop}

\begin{proof}
Let $3\leq j_0\leq n-1$. Each entry $a_{1,j}$, for $3\leq j\leq n-1$, can be expressed by means of $a_{1,j_0}$ and the entries of $T(M)=(b_{i,j})$. Indeed, we have
$$
\begin{array}{rll}
a_{1,j} & = a_{1,j_0} + \displaystyle\sum_{k=j-1}^{j_0-2}{b_{1,k}}, & \text{for\ all}\ 3\leq j<j_0,\\
a_{1,j} & = a_{1,j_0} + \displaystyle\sum_{k=j_0-1}^{j-2}{b_{1,k}}, & \text{for\ all}\ j_0 < j\leq n-1.
\end{array}
$$
Then the entries $a_{1,2}$, $a_{1,j_0}$ and $a_{1,n}$ determine the extension $M$ of $T(M)$.
\end{proof}

Therefore, for every Steinhaus matrix $N$ of size $n-3$, there exist $8$ distinct Steinhaus matrices $M$ of size $n$ such that $T(M)=N$. We can also use this operator to determine parametrizations of multi-symmetric Steinhaus matrices.

\begin{prop}\label{prop7}
Let $M=(a_{i,j})$ be a multi-symmetric Steinhaus matrix of size $n$. Let $j_i$ be an element of the set $\{2i+1,\ldots,n-i\}$ for all $1\leq i\leq\left\lfloor \frac{n-1}{3}\right\rfloor$. Then the matrix $M$ depends on the following parameters:
\begin{itemize}
\item $a_{1,j_1}$ and $\left\{a_{2i,j_{2i}}\ \middle|\ 1\leq i\leq\left\lceil \frac{n}{6}\right\rceil-1\right\}$, for $n$ even,
\item $\left\{a_{2i+1,j_{2i+1}}\ \middle|\ 0\leq i\leq\left\lceil \frac{n-3}{6}\right\rceil-1 \right\}$, for $n$ odd.
\end{itemize}
\end{prop}

\begin{proof}
Let $M=(a_{i,j})$ be a multi-symmetric matrix of size $n$. We consider the sub-matrices $T(M),\ T^2(M)=T(T(M)),\ T^3(M),\ T^4(M),\ \ldots$. By successive application of Proposition~\ref{prop11} on the extension $T^{i-1}(M)$ of $T^i(M)$ and since the entries $a_{i,n-i+1}$, $a_{n-2i+1,n-i+1}$ and $a_{i,2i}$ vanish for all $1\leq i\leq\left\lfloor \frac{n-1}{2}\right\rfloor$ by Proposition~\ref{prop4}, the parametrizations of the multi-symmetric matrix $M$ follow.
\end{proof}

For all positive integers $n$, the number of multi-symmetric Steinhaus matrices of size $n$ immediately follows.

\begin{thm}
Let $n$ be a positive integer. If we denote by $MS(n)$ the number of multi-symmetric Steinhaus matrices of size $n$, then we have
$$
MS(n) = \left\{
\begin{array}{ll}
2^{\left\lceil \frac{n}{6}\right\rceil} & ,\ \text{for}\ n\ \text{even},\\
2^{\left\lceil \frac{n-3}{6}\right\rceil} & ,\ \text{for}\ n\ \text{odd}.
\end{array}
\right.
$$
\end{thm}

\section{Vertex degrees of Steinhaus graphs associated with\\ multi-symmetric Steinhaus matrices}

In this section, we analyse the vertex degrees of a Steinhaus graph associated with a multi-symmetric Steinhaus matrix of size $n$. We begin with the case of doubly-symmetric Steinhaus matrices.

\begin{prop}\label{prop10}
Let $n$ be a positive integer and $G$ be a Steinhaus graph on $n$ vertices whose Steinhaus matrix is doubly-symmetric. Then, for all $1\leq i\leq n$, we have
$$
\deg(V_i) = \deg(V_{n-i+1}).
$$
\end{prop}

\begin{proof}
If we denote by $M=(a_{i,j})$ the Steinhaus matrix associated with the graph $G$, then, for all $1\leq i\leq n$, we have
$$
\deg(V_i) = \sum_{j=1}^{n}{a_{i,j}} = \sum_{j=1}^{n}{a_{n-j+1,n-i+1}} = \sum_{j=1}^{n}{a_{j,n-i+1}} = \deg(V_{n-i+1}).
$$
\end{proof}

We shall now see that, for a Steinhaus graph associated with a multi-symmetric Steinhaus matrix, the knowledge of the vertex degrees modulo $4$ imposes strong conditions on the entries of its Steinhaus matrix. In order to prove this result, we distinguish different cases depending on the parity of $n$.

\begin{prop}\label{prop6}
Let $n$ be an even number and $G$ be a Steinhaus graph on $n$ vertices whose Steinhaus matrix $M=(a_{i,j})$ is multi-symmetric. Then, we have
$$
\begin{array}{l}
\deg(V_1) = \deg(V_n) \equiv a_{1,\frac{n}{2}+1} \pmod{2},\\
\deg(V_2) = \deg(V_{n-1}) \equiv 2a_{1,\frac{n}{2}+1} \pmod{4},\\
\deg(V_3) = \deg(V_{n-2}) \equiv 2a_{2,\frac{n}{2}+1} \pmod{4},\\
\deg(V_{2i}) = \deg(V_{n-2i+1}) \equiv 2a_{2,2i+1} + 2a_{i,2i+1} \pmod{4},\quad \text{for\ all}\ 2\leq i\leq\frac{n}{2}-2.
\end{array}
$$
\end{prop}

\begin{proof}
First, Proposition~\ref{prop4} implies that the entries $a_{i,2i}$ and $a_{2i+1,\frac{n}{2}+i+1}$ vanish for all $1\leq i\leq\frac{n}{2}-1$. This leads to
$$
\begin{array}{l}
\deg(V_1) = \displaystyle\sum_{j=2}^{n}{a_{1,j}} = \sum_{j=2}^{\frac{n}{2}}{(a_{1,j}+a_{1,n-j+2})}+a_{1,\frac{n}{2}+1} \equiv a_{1,\frac{n}{2}+1} \pmod{2},\\
\deg(V_2) = a_{1,2} + \displaystyle\sum_{j=3}^{\frac{n}{2}+1}{(a_{2,j}+a_{2,n-j+3})} = 2\sum_{j=3}^{\frac{n}{2}+1}{a_{2,j}} \equiv 2a_{1,2} + 2a_{1,\frac{n}{2}+1} \equiv 2a_{1,\frac{n}{2}+1} \pmod{4},\\
\deg(V_3) = (a_{1,3}+a_{2,3})+\displaystyle\sum_{j=4}^{\frac{n}{2}+1}{(a_{3,j}+a_{3,n-j+4})}+a_{3,\frac{n}{2}+2} = 2a_{2,3}+2\sum_{j=4}^{\frac{n}{2}+1}{a_{3,j}} \equiv 2a_{2,\frac{n}{2}+1} \pmod{4},
\end{array}
$$
and, for all $2\leq i\leq\frac{n}{2}-2$, we have
$$
\deg(V_{2i})
\begin{array}[t]{l}
= \displaystyle\sum_{j=i+1}^{2i-1}{(a_{j,2i}+a_{2i-j,2i})}+a_{i,2i}+\sum_{j=2i+1}^{\frac{n}{2}+i}{(a_{2i,j}+a_{2i,n-j+2i+1})}\\
= 2\displaystyle\sum_{j=i+1}^{2i-1}{a_{j,2i}} + 2\sum_{j=2i+1}^{\frac{n}{2}+i}{a_{2i,j}}\\
\equiv 2\displaystyle\sum_{j=i+1}^{2i-1}{a_{j,2i+1}} + 2\sum_{j=i+2}^{2i}{a_{j,2i+1}} + 2\sum_{j=2i}^{\frac{n}{2}+i-1}{a_{2i-1,j}} + 2\sum_{j=2i+1}^{\frac{n}{2}+i}{a_{2i-1,j}}\\
\equiv 2a_{i+1,2i+1} + 2a_{2i,2i+1} + 2a_{2i-1,2i} + 2a_{2i-1,\frac{n}{2}+i}\\
\equiv 2a_{i+1,2i+1} + 2a_{2i-1,2i+1} \equiv 2a_{2,2i+1} + 2a_{i,2i+1} \pmod{4}.
\end{array}
$$
Finally, we complete the proof by Proposition~\ref{prop10}.
\end{proof}

\begin{rem}
Let $n$ be an even number. In every Steinhaus graph on $n$ vertices whose Steinhaus matrix is multi-symmetric the fourth vertex $V_4$ has a degree divisible by $4$.
\end{rem}

\begin{prop}\label{prop8}
Let $n$ be an odd number and $G$ be a Steinhaus graph on $n$ vertices whose Steinhaus matrix $M=(a_{i,j})$ is multi-symmetric. Then, we have
$$
\begin{array}{l}
\deg(V_1) = \deg(V_n) \equiv 0 \pmod{2},\\
\deg(V_2) = \deg(V_{n-1}) \equiv 2a_{1,\frac{n+1}{2}} \pmod{4},\\
\deg(V_{2i}) \equiv 2a_{i+1,2i+1} + 2a_{2i-1,2i+1} + 2a_{2i-1,\frac{n-1}{2}+i} \pmod{4},\quad \text{for\ all}\ 2\leq i\leq\frac{n-3}{2},\\
\deg(V_{2i+1}) \equiv 2a_{2,2i+2} \pmod{4},\quad \text{for\ all}\ 1\leq i\leq\frac{n-3}{2}.
\end{array}
$$
\end{prop}

\begin{proof}
Proposition~\ref{prop4} implies that the entries $a_{i,2i}$ and $a_{2i,(n+1)/2+i}$ vanish for all $1\leq i \leq \frac{n-3}{2}$. Since each row and each column of the upper triangular part of $M$ is symmetric, we can use the relation
$$
\sum_{k=1}^{m}a_{i,j+k} \equiv a_{i-1,j} + a_{i-1,j+m} \pmod{2},\quad \text{for\ all}\ 2\leq i<j\leq n-m+1
$$
as in the proof of Proposition~\ref{prop6}, and the results follow.
\end{proof}

\begin{rem}
Let $n$ be an odd number. In every Steinhaus graph on $n$ vertices whose Steinhaus matrix is multi-symmetric the third vertex $V_3$ has a degree divisible by $4$.
\end{rem}

\section{Multi-symmetric Steinhaus matrices\\ of Steinhaus graphs with regularity modulo $4$}

In this section, we consider the multi-symmetric Steinhaus matrices associated with Steinhaus graphs which are regular modulo $4$, i.e. where all vertex degrees are equal modulo $4$. First, we determine an upper bound of the number of these matrices. Two cases are distinguished, according to the parity of $n$.

\begin{thm}\label{thm4}
For all odd numbers $n$, there are at most $2^{\left\lceil \frac{n}{30}\right\rceil}$ multi-symmetric Steinhaus matrices of size $n$ whose associated Steinhaus graphs are regular modulo $4$.
\end{thm}

\begin{proof}
Let $n$ be an odd number and $M=(a_{i,j})$ a multi-symmetric Steinhaus matrix of size $n$. By Proposition~\ref{prop7}, the matrix $M$ depends on the parameters $a_{2i+1,\frac{n+1}{2}+i}$ for $0\leq i\leq \left\lceil \frac{n-3}{6}\right\rceil-1$. If the Steinhaus graph associated with $M$ is regular modulo $4$, then Proposition~\ref{prop8} implies that $a_{2,2j}=0$ for all $2\leq j\leq \frac{n-1}{2}$ and thus
$$
a_{2i,2j} = \sum_{k=0}^{i-1}a_{2,2j-2k} =0,
$$
for all $1\leq i<j\leq \frac{n-1}{2}$.
\par If $n\equiv 1\pmod{4}$, then $\frac{n+1}{2}$ is odd and
$$
a_{4i+1,\frac{n+1}{2}+2i} = a_{4i,\frac{n-1}{2}+2i} + a_{4i,\frac{n+1}{2}+2i} = 0,
$$
for all $0\leq i\leq \left\lfloor \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rfloor$. Therefore the matrix $M$ can be parametrized by
$$
\left\{ a_{4i+3,\frac{n+3}{2}+2i}\ \middle|\ 0\leq i\leq m-1\right\},
$$
with
$$
m=\left\lceil \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rceil.
$$
Suppose that we know the $p$ parameters in
$$
P = \left\{ a_{4i+3,\frac{n+3}{2}+2i}\ \middle|\ m-p\leq i\leq m-1\right\}.
$$
Then, by Proposition~\ref{prop7} again, the multi-symmetric matrix $T^{4(m-p)-1}(M)$ can be parametrized by $P$. Therefore the entries
$$
\left\{ a_{i,2i+1}\ \middle|\ 4(m-p)\leq i\leq \frac{n-1}{2}-2(m-p)\right\}
$$
in $T^{4(m-p)-1}(M)$ depend on the parameters in $P$. Moreover, if the Steinhaus graph associated with $M$ is regular modulo $4$, then Proposition~\ref{prop8} implies that
$$
a_{2,2i+1} = a_{2i-1,2i+1} \equiv a_{i+1,2i+1} + a_{2i-1,\frac{n-1}{2}+i} \equiv a_{i+1,2i+1} + a_{\left(\frac{n+1}{2}-i\right)+1,2\left(\frac{n+1}{2}-i\right)+1} \pmod{2},
$$
for all $1\leq i\leq\frac{n-1}{2}$. If the inequality
$$
\frac{n+1}{2}-4(m-p)\geq4(m-p)
$$
holds, then the entries $a_{2,2i+1}$ depend on the parameters in $P$ for all $4(m-p)\leq i\leq \frac{n+1}{2}-4(m-p)$. Since we have $a_{2,2i}=0$ for all $4(m-p)\leq i\leq \frac{n+3}{2}-4(m-p)$, it follows that the entries
$$
\left\{ a_{i,j}\ \middle|\
\begin{array}{c}
2 \leq i \leq n+5-16(m-p)\\
8(m-p)+i-1 \leq j \leq n+3-8(m-p)
\end{array} \right\}
$$
depend on the parameters in $P$. Suppose now that $p$ is solution of the following inequality
$$
n+5-16(m-p) \geq 4(m-p)-1.
$$
Therefore the extension $M$ of $T^{(4(m-p)-1)}(M)$ depends on the entries $a_{i,n+3-8(m-p)}$ for $2\leq i\leq 4(m-p)-1$ and $a_{1,\frac{n+1}{2}}$ which vanishes by Proposition~\ref{prop8}. Thus, all the entries of the matrix $M$ depend on the $p$ parameters in $P$. Finally, a solution of this inequality can be obtained when
$$
p=\left\lceil \frac{n}{30}\right\rceil \geq \left\lceil \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rceil-\frac{n+6}{20}.
$$
\par If $n\equiv3\pmod{4}$, then $\frac{n+1}{2}$ is even and
$$
a_{4i+3,\frac{n+3}{2}+2i} = a_{4i+2,\frac{n+1}{2}+2i} + a_{4i+2,\frac{n+3}{2}+2i} = 0,
$$
for all $0\leq i\leq \left\lceil \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rceil-1$. Therefore the matrix $M$ can be parametrized by
$$
\left\{ a_{4i+1,\frac{n+1}{2}+2i}\ \middle|\ 0\leq i\leq m\right\}
$$
with
$$
m=\left\lfloor \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rfloor.
$$
As above, in the case $n\equiv1\pmod{4}$, we can prove that all the entries of the matrix $M$ depend on the $p$ parameters in
$$
\left\{ a_{4i+1,\frac{n+1}{2}+2i}\ \middle|\ m-p+1\leq i\leq m\right\}
$$
if $p$ is solution of the following inequality
$$
n-16(m-p)-4 \geq 4(m-p)+1.
$$
A solution is obtained when
$$
p = \left\lceil \frac{n}{30}\right\rceil \geq \left\lfloor \frac{\left\lceil \frac{n-3}{6}\right\rceil-1}{2}\right\rfloor - \frac{n-5}{20}.
$$
\end{proof}

\begin{thm}
For all even numbers $n$, there are at most $2^{\left\lceil \frac{n}{24}\right\rceil}$ multi-symmetric Steinhaus matrices of size $n$ whose associated Steinhaus graphs are regular modulo $4$.
\end{thm}

\begin{proof}[Sketch of proof]
Similar to the proof of Theorem~\ref{thm4}. Let $M=(a_{i,j})$ be a multi-symmetric Steinhaus matrix of even size $n$. First, by Proposition~\ref{prop7}, for all positive integers $p<m-1$ with $m=\left\lceil \frac{n}{6}\right\rceil$, the multi-symmetric Steinhaus matrix $T^{2\left(m-p-1\right)}(M)$ can be parametrized by the $p$ entries in
$$
P = \left\{ a_{2i,4i+1}\ \middle|\ m - p \leq i\leq m-1\right\}.
$$
Moreover, if the Steinhaus graph associated with $M$ is regular modulo $4$, then Proposition~\ref{prop6} implies that $a_{1,\frac{n}{2}+1}=0$ and $a_{2,2i+1} = a_{i,2i+1}$ for all $2\leq i\leq \frac{n}{2}-1$. It follows that the entries $a_{2i,n-2(m-p)+1}$ also depends on the parameters in $P$ for all $1\leq i\leq \frac{n}{2}-3(m-p)+2$. Finally, we can see that, if $p$ is solution of the following inequality
$$
\frac{n}{2}-3(m-p)+2 \geq m-p-1,
$$
then, as in the proof of Proposition~\ref{prop7}, the extension $M$ of $T^{2(m-p-1)}(M)$ depends on the entries $a_{2i,n-2(m-p)+1}$ for $1\leq i\leq m-p-1$ and thus all the entries of the matrix $M$ can be expressed by means of the $p$ parameters in $P$. We conclude the proof by observing that the inequality is obtained when
$$
p = \left\lceil \frac{n}{24}\right\rceil \geq \left\lceil \frac{n}{6}\right\rceil - \frac{n+6}{8}.
$$
\end{proof}

Using these explicit parametrizations of the multi-symmetric Steinhaus matrices whose Steinhaus graphs are regular modulo $4$, we obtain the following result by computer search:

\begin{comp}
For all positive integers $n\leq 1500$, the zero-edge graph on $n$ vertices is the only Steinhaus graph on $n$ vertices with a multi-symmetric Steinhaus matrix and which is regular modulo $4$.
\end{comp}

This result can be easily proved for all odd numbers in the special case of regular Steinhaus graphs on $n$ vertices whose Steinhaus matrices are multi-symmetric.

\begin{thm}
For all odd numbers $n$, there is no regular Steinhaus graph on $n$ vertices whose Steinhaus matrix is multi-symmetric, except the zero-edge graph on $n$ vertices.
\end{thm}

\begin{proof}
Let $n$ be an odd number. Let $G$ be a regular Steinhaus graph on $n$ vertices and $M=(a_{i,j})$ its Steinhaus matrix. Then Proposition~\ref{prop8} implies that
$$
\deg(V_i) \equiv 0 \pmod{4},
$$
for all $1\leq i\leq n$ and
$$
a_{2,2i+2} = 0,
$$
for all $1\leq i\leq\frac{n-3}{2}$. If we denote by $\oplus$ the addition in $\mathbb{F}_2$ and $+$ the addition in the integers, then we obtain
$$
\deg(V_3)
\begin{array}[t]{l}
= a_{1,3} + a_{2,3} + \displaystyle\sum_{j=4}^{n}{a_{3,j}} = (a_{1,2}\oplus a_{2,3}+a_{2,3}) + \sum_{j=2}^{\frac{n-3}{2}}{(a_{3,2j+1}+a_{3,2j+2})} + 2a_{3,n}\\
= 2a_{2,3} + \displaystyle\sum_{j=2}^{\frac{n-3}{2}}{(a_{2,2j}\oplus a_{2,2j+1} + a_{2,2j+1}\oplus a_{2,2j+2})} + 2(a_{2,n-1}\oplus a_{2,n})\\
= 2\displaystyle\sum_{j=1}^{\frac{n-1}{2}}{a_{2,2j+1}} = 2(a_{1,2}+\sum_{j=3}^{n}{a_{2,j}}) = 2\times\deg(V_2).
\end{array}
$$
This leads to $\deg(V_i)=0$ for all $1\leq i\leq n$ and thus $G$ is the zero-edge graph on $n$ vertices.
\end{proof}

Finally, the above computational result permits us to extend the verification of Conjecture~\ref{conj2} up to $n\leq 1500$ vertices. Indeed, as proved in the remark following Theorem~\ref{thm5}, for a Steinhaus graph $G$ on $2n$ vertices, if $G\setminus\{V_1,V_{2n}\}$ is the zero-edge graph on $2n-2$ vertices, then $G$ is the star graph on $2n$ vertices which is not a regular graph. Therefore, by Theorem~\ref{thm5}, we obtain

\begin{thm}
There is no regular Steinhaus graph of odd degree on $2<n\leq 1500$ vertices.
\end{thm}

\section*{Acknowledgments}

The author would like to thank Shalom Eliahou for introducing him to the subject and for his help in preparing this paper.

\nocite{*}
\bibliographystyle{plain}
\bibliography{biblio}

\noindent Jonathan Chappelon\\
Laboratoire de Math\'ematiques Pures et Appliqu\'ees Joseph Liouville, FR CNRS 2956\\
Universit\'e du Littoral C\^ote d'Opale\\
50 rue F. Buisson, B.P. 699, F-62228 Calais Cedex, France\\
e-mail: jonathan.chappelon@lmpa.univ-littoral.fr

\end{document}


text:
/-
Copyright (c) 2021 OpenAI. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kunhao Zheng, Stanislas Polu, David Renshaw, OpenAI GPT-f
-/
import mathzoo.imports.miniF2F

open_locale nat rat real big_operators topological_space

theorem aime_1983_p9
  (x : ℝ)
  (h₀ : 0 < x ∧ x < real.pi) :
  12 ≤ ((9 * (x^2 * (real.sin x)^2)) + 4) / (x * real.sin x) :=
begin
  let y := x * real.sin x,
  rw ← mul_pow,
  change 12 ≤ (9 * y^2 + 4) / y,
  refine (le_div_iff _).mpr _,
  apply mul_pos h₀.1,
  apply real.sin_pos_of_pos_of_lt_pi h₀.1 h₀.2,
  suffices : 0 ≤ (3 * y - 2)^2, nlinarith,
  exact pow_two_nonneg (3 * y - 2),
end

subset_name: curated


TITLE: System normaliser and chief series of a finite solvable group
QUESTION [0 upvotes]: Definition: A chief series of a finite group $G$ is a maximal normal series of $G$. In other words, $H_i \unlhd G$ for $i=0, \ldots, n$. $$ 1_G = H_0 \leqslant H_1 \leqslant H_2 \leqslant \dots \leqslant H_n = G$$ and there exists no normal subgroups strictly contained between $H_i$ and $H_{i+1}$.
Definition: Let $G$ be a finite solvable group and $\Sigma \in \text{H}(G)$, the set of Hall systems of $G$. The normaliser of $\Sigma$ is defined as $$ N_G(\Sigma) = \{ g\in G \,|\, H=H^g \text{ for all} H \in \Sigma \}.$$ A system normaliser of $G$ is a subgroup of the form $N_G(\Sigma)$ for some $\Sigma \in \text{H}(G)$.
Lemma: Let $D= N_G(\Sigma)$.  If $H/K$ is a chief factor of $G$ such that $H/K \leq Z(G/K)$ i.e. it is central then $D$ covers $H/K$. That is to say, $H \leq DK$.

Let $G$ be a finite solvable group with $N$ a minimal normal subgroup of $G$, $HN \unlhd G$ and $y \in G$ such that $G = HN \langle y \rangle$. Let $D= N_G(\Sigma)$ for some Hall system $\Sigma$ of $G$. Then $G = DHN$

I know that $G/HN \cong \langle y \rangle$, so that $G/HN$ is cylic and so abelian. Thus $G/HN = Z(G/HN)$. Thus for any chief series of $G$ passing through $HN$, the chief factors above $HN$ are all central, and $D$ covers them by the Lemma.
I'm not sure how $G = DHN$ follows. Is it possible that $G/HN$ is a chief factor of some chief series of $G$?. If this is the case then $D$ covers $G/HN$ so that $G \leq DHN$. Thus $G=DHN$.

REPLY [0 votes]: Consider the chief series of $G$ given by $$\{1_G \} = B_0 \leqslant B_1 \leqslant \dots \leqslant B_n = G.$$ Since we are factoring out $HN$ from $G$ in $G/HN$, we may assume that $HN = \{1_G \}$. In this case, we have that $G/\{1_G \} \cong G$, which is cyclic, and hence abelian. Moreover, $B_{i+1}/B_{i} \leq G/B_i = Z(G/B_i)$ for $i=0, \ldots, n-1$, since $G/B_i$ is abelian. By the Lemma, $D$ covers $B_{i+1}/B_{i}$ for $i=0, \ldots, n-1$. Now $|G| = \prod \limits_{i=0}^{n-1} [B_{i+1} : B_i]$. Intersecting the chief series of $G$ with $D$ yields $|D| = \prod \limits_{i=0}^{n-1} [B_{i+1} \cap D : B_i \cap D]$. Since $D$ covers $B_{i+1}/B_{i}$ for $i=0,.., n-1$, we have that $[B_{i+1} \cap D : B_i \cap D] = [B_{i+1} : B_i ]$ for $i=0,.., n-1$. Therefore $|D| =\prod \limits_{i=0}^{n-1} [B_{i+1} : B_i] = |G|$. This implies that $G = D$, and so $G = DHN$


TITLE: G-equivariant bundle
QUESTION [0 upvotes]: This question is crossposted from mathstackexchange.
Suppose $X$ is a smooth projective variety over $k$ and $G$ a finite group acting on $X$ with $\mathrm{char}(k)$ does not divide the order of $G$. Let $\mathcal{E}$ be a $G$-equivariant vector bundle. Then one has a $G$ action on $\mathbb{P}(\mathcal{E})$. Now consider $\mathcal{F}$ a $G$-equivariant vector bundle on $X$. Is $\pi^*\mathcal{F}$ a $G$-equivariant sheaf on $\mathbb{P}(\mathcal{E})$? (Here $\pi:\mathbb{P}(\mathcal{E})\rightarrow X$)

REPLY [0 votes]: "$G$-equivariant" is not a property of a sheaf, it is an extra structure. So you have to define an action of $G$ on $\pi ^*\mathcal{F}$ compatible with the action on $\mathbb{P}(\mathcal{E})$. There is an obvious one: $\pi ^*\mathcal{F}$ is the fibre product $\mathbb{P}(\mathcal{E})\times _X\mathcal{F}$,   $G$ acts on both factors, you take the product action.


TITLE: Absolute maximum calculus 3
QUESTION [0 upvotes]: Consider the function $f(x,y) = (x -1)^2 + 3(y-2)^2$ and the region $R = \{(x,y) : y \leq x\}$. If it exists, find the absolute maximum of $f(x,y)$ on $R$. If it does not exist then say so.
I first found the partial derivatives of f and I got the critical point (1, 2). However, that is not in the region. So the next thing I tried was to check the boundary, but I wasn't sure how to do that. Any help would be appreciated.

REPLY [0 votes]: The absolute maximum certainly does not exist because you can make $$ arbitrarily large by making both $$ and $$ arbitrarily large (within $$). (Let $ \to 10^{100}$ and $y \to 10^{100}−1$)....

I have a feeling you're not posting the right question.

REPLY [0 votes]: The boundary is $y=x$.  Plug it in.   We get $(x-1)^2+3(x-2)^2=4x^2-14x+13$.
This (polynomial) function is unbounded;  hence there's no max.


TITLE: Understanding Leibniz rule in the framework of Banach space.
QUESTION [3 upvotes]: Let $E,F_1,F_2,G$ be Banach spaces and $U \subseteq E$ be an open subset. Let $f_j : U \longrightarrow F_j$ be $C^r$ maps and $B : F_1 \times F_2 \longrightarrow G$ be a bounded bilinear map. Then $g : x \mapsto B(f_1(x),f_2(x))$ is $C^r.$ Also for $k=1,2,\cdots,r$ we have $$D^kg(x) (h_1,h_2,\cdots,h_k) = \sum\limits_{j=0}^{k} \binom {k} {j} B\left (D^jf_1(x) (h_1,h_2,\cdots,h_j) ,D^{k-j}f_2(x) (h_{j+1},h_{j+2}, \cdots, h_k) \right ).$$

I have managed to prove that $g$ is $C^1$ and for any $h \in E$ we have $$Dg(x) (h) = B \left (f_1(x),Df_2(x)(h) \right ) + B \left (Df_1(x)(h),f_2(x) \right ).$$
Now how do I prove that $g$ is $C^k$ for $k \gt 1\ $? How do I prove first that $Dg \in C^1\ $? Here $Dg : U \longrightarrow \mathcal L(E,G).$ Can $Dg$ be written as a composition of Frechet differentiable functions? Can anybody please give me some suggestion? Then I will try to prove it for any $k \gt 1.$
Thanks for your time.
EDIT $:$ What I get is that $$D^2 g(x) (h_1,h_2) = B \left (f_1(x),D^2f_2 (x) (h_1,h_2) \right ) + B \left (Df_1(x)(h_1), Df_2 (x) (h_2) \right ) + B \left (Df_1(x) (h_2), Df_2 (x) (h_1) \right ) + B\left (D^2f_1(x) (h_1,h_2),f_2(x) \right).$$ But I don't know why it has been claimed in the proposition that $$B \left (Df_1(x)(h_1), Df_2 (x) (h_2) \right ) = B \left (Df_1(x) (h_2), Df_2 (x) (h_1) \right ).$$

REPLY [2 votes]: I won't prove the $k^{th}$ product rule formula, because it is already tedious enough to do in one-dimension (though if you keep your cool, it is just a matter of induction and carefully playing around with some binomial coefficient identities... try to mimic the one-dimensional proof as much as possible).
As a general remark, whenever you want to prove certain maps are of class $C^k$, very useful are the canonical injections and projections $\iota_i:V_i\to V_1\times V_2$, and the canonical projections $\pi_i:V_1\times V_2\to V_i$ (for example $\iota_1(x):=(x,0)$ and $\pi_1(x,y):=x$). These are bounded linear maps hence $C^{\infty}$ (their second derivative vanishes).
For your particular question, there are a few ways of arguing things, depending on how much stuff you've already proven. For example, if you've already proven that the composition of $C^k$ functions is $C^k$, more precisely:

Let $k\geq 1$ be an integer, $E,F,G$ be Banach spaces (all over the same field), $U\subset E$, $V\subset F$ be non-empty open sets, $f:U\to V$, $g:V\to G$ be $C^k$ functions. Then, $g\circ f:U\to G$ is also $C^k$.

then this is quite simple. Here's how we apply in your specific case: we can write
\begin{align}
g= B\circ \left(\iota_1\circ f_1 + \iota_2\circ f_2\right)
\end{align}
Just to see that everything makes sense, observe that $f_1:U\to F_1$, $\iota_1:F_1\to F_1\times F_2$ so the composition is $\iota_1\circ f_1:U\to F_1\times F_2$. Similarly, $\iota_2\circ f_2:U\to F_1\times F_2$. Hence, their sum is also a function $U\to F_1\times F_2$. So, finally by composing with $B:F_1\times F_2\to G$, we get the function $g:U\to G$.
Now, $f_1,f_2$ are $C^r$ by assumption, $\iota_1,\iota_2$ are bounded and linear (which implies $C^{\infty}$ and hence trivially also $C^r$), so by the remark above, $\iota_1\circ f_1$ and $\iota_2\circ f_2$ are $C^r$ functions. Therefore, their sum is also $C^r$ (the fact that sum of $C^r$ functions is $C^r$ is an easy exercise in induction and the simple rule that $D(\alpha+\beta)_x= D\alpha_x+D\beta_x$). Finally $B$ is a bounded bilinear mapping, it is also $C^{\infty}$ hence $C^r$ (more generally, for any bounded $p$-multilinear mapping, if you take its $(p+1)^{th}$ derivative you get $0$... again an exercise in induction... therefore it is easily seen to be $C^{\infty}$). Therefore, $g=B\circ \left(\iota_1\circ f_1 + \iota_2\circ f_2\right)$ is the composition of $C^r$ functions hence $C^r$. In short,
\begin{align}
g= B\circ \left(\iota_1\circ f_1 + \iota_2\circ f_2\right) ``=" C^{\infty}\circ \left(C^{\infty}\circ C^r + C^{\infty}\circ C^r\right) = C^r
\end{align}

Edit:
Your calculation is right, the given formula is wrong, because the formula on the right is not symmetric in $h_1,\dots, h_k$. For example, when $k=2$, the given formula says that
\begin{align}D^2g(x)(h_1,h_2) &= B(f_1(x), D^2f_2(x)(h_1,h_2)) + 2B(Df_1(x)(h_1), Df_2(x)(h_2)) \\
&+ B(D^2f_1(x)(h_1,h_2),f_2(x)).
\end{align}
The LHS $D^2g(x)$ being a second derivative must be symmetric in $h_1,h_2$, but the RHS is clearly not symmetric, so the given formula is wrong. If I'm not mistaken, the correct formula is obtained by symmetrizing your given formula.
So, if we let $\lambda_k(x):\underbrace{E\times\cdots \times E}_{\text{$k$ times}}\to G$ be the multilinear map
\begin{align}
&\lambda_k(x)(h_1,\dots, h_k)\\
&:=
\sum_{j=0}^k \binom{k}{j} B\left (D^jf_1(x) (h_1,h_2,\cdots,h_j) ,D^{k-j}f_2(x) (h_{j+1},h_{j+2}, \cdots, h_k) \right ),
\end{align}
then $D^kg_x = \text{Sym}_k(\lambda_k(x))$, or more explicitly,
\begin{align}
D^kg(x)(h_1,\dots, h_k)&=\dfrac{1}{k!}\sum_{\sigma\in S_k}\lambda_{k}(x)\left(h_{\sigma(1)}, \dots, h_{\sigma(k)}\right),
\end{align}
where $S_k$ is the set of all permutations on $k$ objects (i.e the set of all bijections $\sigma:\{1,\dots, k\}\to \{1,\dots, k\}$).


text:
\DOC mk_list

\TYPE {mk_list : term list * hol_type -> term}

\SYNOPSIS
Constructs object-level list from list of terms.

\DESCRIBE
{mk_list([`t1`;...;`tn`],`:ty`)} returns {`[t1;...;tn]:(ty)list`}.
The type argument is required so that empty lists can be constructed. If you
know the list is nonempty, you can just use {mk_flist} where this is not
required.

\FAILURE
Fails with if any term in the list is not of the type specified as the second
argument.

\EXAMPLE
{
  # mk_list([`1`; `2`],`:num`);;
  val it : term = `[1; 2]`

  # mk_list([],`:num`);;
  val it : term = `[]`

  # type_of it;;
  val it : hol_type = `:(num)list`
}

\SEEALSO
dest_cons, dest_list, is_cons, is_list, mk_cons, mk_flist.

\ENDDOC