# HFL-RC System at SemEval-2018 Task 11: Hybrid Multi-Aspects Model for
Commonsense Reading Comprehension

Zhipeng Chen∗†,Yiming Cui∗†, Wentao Ma†, Shijin Wang†, Ting Liu‡ Guoping Hu†
†Joint Laboratory of HIT and iFLYTEK (HFL), iFLYTEK Research, Beijing, China
‡Research Center for Social Computing and Information Retrieval (SCIR),
Harbin Institute of Technology, Harbin, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

This paper describes the system which got the state-of-the-art results at
SemEval-2018 Task 11: Machine Comprehension using Commonsense Knowledge. In
this paper, we present a neural network called Hybrid Multi-Aspects (HMA)
model, which mimic the human’s intuitions on dealing with the multiple-choice
reading comprehension. In this model, we aim to produce the predictions in
multiple aspects by calculating attention among the text, question and
choices, and combine these results for final predictions. Experimental results
show that our HMA model could give substantial improvements over the baseline
system and got the first place on the final test set leaderboard with the
accuracy of 84.13%.

††footnotetext: ∗Equal contribution.

##  1 Introduction

Machine Reading Comprehension (MRC) has become a spotlight topic in recent
natural language processing field. MRC consists of various subtasks, such as
cloze-style reading comprehension (Hermann et al., 2015; Hill et al., 2015;
Cui et al., 2016, 2018), span-extraction reading comprehension (Rajpurkar et
al., 2016) and open-domain reading comprehension (Chen et al., 2017), etc. One
key problem in reading comprehension is that how the machine utilizeS the
commonsense knowledge for real-life reading comprehension. In the SemEval-2018
Task 11: Machine Comprehension using Commonsense Knowledge (Ostermann et al.,
2018), the organizers provide narrative texts about everyday activities and
require the participants to build a system for answering questions based on
this text. To tackle this problem, in this paper, we present a novel model
called Hybrid Multi-Aspects (HMA) model. The main features of our model can be
concluded as follows.

  * •

Our model is mainly based on the neural network approach without using any
external knowledge, such as script knowledge, etc.

  * •

We aim to produce the predictions in multiple aspects by calculating attention
among the text, question and choices, and combine these results for final
predictions.

  * •

We add additional features on the embedding representations for the text,
question and choices, including word matching feature and part-of-speech tags,
etc.

##  2 System Description

We will first give a brief introduction of the SemEval-2018 Task 11. Then the
pre-processing and the proposed Hybrid Multi-Aspects model will be illustrated
afterwards. A quick glance of the neural architecture of the HMA model is
depicted in Figure 1.

###  2.1 Task Description

Given a short context about the narrative texts about everyday activities and
several following questions about the context, the participants are required
to build a system to solve the question by choosing the correct answer from
two choice choices. The participants are encouraged to use external knowledge
to improve their systems and there is no restrictions. For more details,
please infer Ostermann et al. (2018).

###  2.2 Pre-processing

We describe the pre-processing procedure on the evaluation data, which can be
listed as follows.

  1. 1.

All punctuations are removed.

  2. 2.

All words are lower-cased.

  3. 3.

All sentences are tokenized by Natural Language Toolkit (NLTK) (Bird et al.,
2009).

Figure 1: Neural architecture of our Hybrid Multi-Aspects (HMA) model. Note
that, there are two choices processed in parallel.

###  2.3 Embedding Layer

In this layer, we aim to project text, question and choices into embedding
representations. The final embedding representations are composed by three
components, which can be listed as follows.

  1. 1.

Word embedding: We use pre-trained GloVe embedding (Pennington et al., 2014)
for word representations, whose size is 100d (d for dimension).

  2. 2.

Char embedding: We use randomly initialized embedding matrix for char-level
embeddings, whose size is 8d. We use 1D-convolution operation with filter
length of 5 and output size of 100d. Then we apply max-over-time-pooling to
obtain the final representation, whose size is 100d.

  3. 3.

Feature embedding: We also adopt several hand-crafted features for enhancing
the word representations. In this paper, we adopt three features which can be
illustrated as follows.

    1. (a)

Part-of-Speech: We use NLTK (Bird et al., 2009) for part-of-speech tagging for
each word in the text, question and choices. In this paper, we assign
different trainable vectors with size of 16d for each part-of-speech tag.

    2. (b)

Word matching: Taking the text as an example, if the text word appear in
question or choice, we set this feature as 1. If not, set it as 0. In this
way, we can also add this feature to the question and choice.

    3. (c)

Word fuzzy matching: Similar to the ‘word matching’ feature, but we loosen the
matching criteria as partial matching. For example, we regard ‘teacher’ and
‘teach’ as fuzzy matching, because the string ‘teacher’ is partially matched
by ‘teach’.

After obtaining three parts of the embeddings, the final representation is the
concatenation of three embeddings, forming the size of 100d+100d+16d+2d=218d.

###  2.4 RNN Layer

After obtaining the embedding representations $E$, we first feed this into a
shared Highway network (Srivastava et al., 2015) across the text, question and
choices. The output activation is chosen as $\tanh$.

$HW=\tanh(Highway(E))$ (1)

After highway network, we get text, question and choices’ presentation
$HW_{T}\in{\mathbb{R}}^{t\times e}$, $HW_{Q}\in\mathbb{R}^{q\times e}$ and
$HW_{C}\in\mathbb{R}^{cn\times c\times e}$, where $t$, $q$, $c$ and $cn$
represent the text max length, question max length , choice max length and the
number of choices respectively. Then we use Bi-directional LSTM (Graves and
Schmidhuber, 2005) and concatenate the forward and backward hidden
representations to obtain the contextual representations of text
$B_{T}\in{\mathbb{R}}^{t\times h}$, question $B_{Q}\in\mathbb{R}^{q\times h}$
and choices $B_{C}\in\mathbb{R}^{cn\times c\times h}$, where $h$ presents Bi-
LSTM hidden size. Note that, we use separated Bi-LSTM (without sharing
weights) for the text, question and choices.

$\displaystyle B_{T}=\text{Bi-LSTM}(HW_{T})$ (2) $\displaystyle
B_{Q}=\text{Bi-LSTM}(HW_{Q})$ (3) $\displaystyle B_{C}=\text{Bi-LSTM}(HW_{C})$
(4)

###  2.5 Attention Layer

After obtaining the contextual representations of the text, question and
choices, we will calculate the attentions between different combinations in
order to characterize the choices in multiple aspects. In this paper, we aim
to obtain three representations

  1. 1.

choice-aware text representation $H_{CT}$

  2. 2.

choice-aware question representation $H_{CQ}$

  3. 3.

self-attended question representation $H_{QQ}$

First, we will calculate choice-aware text representation $H_{CT}$ to extract
the choice-relevant part from text representation. Following Cui et al.
(2017), we first calculate dot similarity between each word in the text and
choice to obtain the matching matrix. Then we apply row-wise softmax to obtain
individual text-level attention with respect to each choice word, denoted as
$M_{CT}\in\mathbb{R}^{c\times t}$.

$\displaystyle M^{{}^{\prime}}_{CT}=B_{C}\cdot B_{T}^{T}$ (5) $\displaystyle
M_{CT}=softmax(M^{{}^{\prime}}_{CT})$ (6)

Then we will get choice-aware text representation
$H_{CT}\in\mathbb{R}^{c\times 2h}$. Note that, we will also concatenate choice
LSTM representation $B_{C}$ to enhance the representation power.

$\displaystyle H^{{}^{\prime}}_{CT}=M_{CT}\cdot B_{T}$ (7) $\displaystyle
H_{CT}=concat[H^{{}^{\prime}}_{CT}~{};~{}B_{C}]$ (8)

In the same way, we can also obtain the choice-aware question representation
$H_{CQ}\in\mathbb{R}^{c\times 2h}$ and the question-aware text representation
$H_{QT}\in\mathbb{R}^{q\times 2h}$. However, in order to get further extract
question information, we apply additional self-attention procedure to obtain
self-attention matching matrix $M_{QQ}\in\mathbb{R}^{q\times q}$.

$\displaystyle M^{{}^{\prime}}_{QQ}=H_{QT}\cdot H_{QT}^{T}$ (9) $\displaystyle
M_{QQ}=softmax(M^{{}^{\prime}}_{QQ})$ (10)

Then we will get self-attended question representation
$H_{QQ}\in\mathbb{R}^{q\times 2h}$.

$\displaystyle H^{{}^{\prime}}_{QQ}=M_{QQ}\cdot B_{Q}$ (11) $\displaystyle
H_{QQ}=concat[H^{{}^{\prime}}_{QQ}~{};~{}B_{q}]$ (12)

###  2.6 Answer Layer

In this module, we will utilize the multi-aspect representations from
previousl layer to get a hybrid prediction. First, we will calculate the
similarity between the choice-aware text representation $H_{CT}$ and self-
attended question representation $H_{QQ}$ to obtain the deep matching matrix
$D_{CT}$. Similarly, we can also calculate the similarity between the choice-
aware question representation $H_{CQ}$ and self-attended question
representation $H_{QQ}$ to obtain the deep matching matrix $D_{CQ}$.

$\displaystyle D_{CT}=H_{CT}\cdot H^{T}_{QQ}$ (13) $\displaystyle
D_{CQ}=H_{CQ}\cdot H^{T}_{QQ}$ (14)

Then we will apply a element-wise weight $W_{CT}\in\mathbb{R}^{c\times q}$ and
get the weighted sum of $D_{CT}$ and output a scalar value. Note that, we have
two choices, so the final output should be $A_{CT}\in\mathbb{R}^{1\times 2}$.
In the same way, we can also calculate $A_{CQ}\in\mathbb{R}^{1\times 2}$.

$\displaystyle A_{CT}=\sum D_{CT}\odot W_{CT}$ (15) $\displaystyle A_{CQ}=\sum
D_{CQ}\odot W_{CQ}$ (16)

Finally, we apply softmax function to $A_{CT}$ and $A_{CQ}$ and sum the
probabilities to get final predictions $A$.

$\displaystyle A=softmax(A_{CT})+softmax(A_{CQ})$ (17)

###  2.7 Training Criterion

We use categorical cross entropy to calculate loss between the predicted
answer probability $A$ and real answer.

##  3 Experiments

###  3.1 Experimental Setups

We listed the main hyper-parameters of our model in Table 1. The word
embeddings are initialized by the pre-trained GloVe word vectors (Common
Crawl, 6B tokens, 100-dimension) (Pennington et al., 2014). The words that do
not appear in the pre-trained word vectors are set to the ‘unk’ token and
initialized accordingly. We use Adam for weight optimizations with default
parameters. The models are built on Keras (Chollet, 2015) with Theano backend
(Theano Development Team, 2016). We choose our model by the performance of the
development set.

Symbol | Descriptions | #
---|---|---
t | Text max length | 300
q | Question max length | 20
cn | Number of choices | 2
e | Embedding size | 218
h | Bi-LSTM output size | 200
c | choice max length | 10
Table 1:  Hyper-parameter settings of our system.

###  3.2 Results

The experimental results are shown in Table 2. We also listed some of the top-
ranked systems in this evaluation111Full SemEval-2018 Task 11 leaderboard can
be accessed through:
https://competitions.codalab.org/competitions/17184#results. As we can see
that our single model could give substantial improvements over Simple RNN
baseline system by 12.78% on development set. For further improve the
performance, we carried out 7-ensemble by voting approach produced by each
single system. The results show that the ensemble system could give further
improvements where 1.98% and 3.19% gains on development and test set
respectively. When compared to the several top-ranked systems, our HMA model
surpasses all the competitors and got on the first place in SemEval-2018 Task
11.

Model | Dev | Test
---|---|---
Simple RNN | 71.70% | -
HMA Model (single) | 84.48% | 80.94%
HMA Model (ensemble) | 86.46% | 84.13%
Yuanfudao (BananaTree) | - | 83.95%
MITRE (guidoz) | - | 82.27%
(jiangnan) | - | 80.91%
Rusalka (minerva) | - | 80.48%
SLQA (mingyan) | - | 79.94%
Table 2:  Experimental results. Top-ranked participant’s systems are also
included.

##  4 Discussion

To have a better understanding of the data, we divided the data into different
question types, which can be seen in Figure 2. As we can see that the yes/no
question takes up 27% proportion, which is quite different from most of the
other reading comprehension datasets. The yes/no questions require better
handling the negation and deeper understanding in question.

Figure 2: Proportions of different question types.

Another observation is that, different from SQuAD dataset (Rajpurkar et al.,
2016), the choices are not extracted from the text but written by the human.
So there are many questions that the ordinary word matching failed to give
correct answer. For example, the example shown in Figure 3, the choice ‘dirty’
is not exactly match the word ‘dirt’ in passage, which add difficulties in
solving these problems. In our model, we add additional partial matching
feature to indicate the underlying relations. The final results show that
adding partial matching feature could give an improvement of 1%$\sim$2% in
accuracy, indicating that the feature is helpful for the model to identify the
words that have similar meanings. Also, we have tried to use word stemming to
restore the word to its stemming form, we observed a significant drop in the
final performance, suggesting that a much powerful model is needed to further
tackle these problems.

Figure 3:  Example of the partial matching problem.

##  5 Conclusion

In this system description, we propose a novel neural network system called
Hybrid Multi-Aspects (HMA) model for the SemEval-2018 Task 11. In this model,
we aim to produce multi-aspect output and combine them for final predictions.
We adopt a simple dot product to measure the similarity between the text,
question and choices. We also enhanced the question representations by using
self-attention mechanism. The final predictions are obtained by accumulating
the probabilities from various aspects. The final leaderboard provided by the
task officials shows that the proposed HMA model got the first place among 24
participants with the accuracy of 84.13%. In the future, we would like to
investigate how to effectively adopt the external knowledge into machine
reading comprehension model and would like to focus on solving the questions
that is less likely answered by statistical data.

## Acknowledgments

This work was supported by the National 863 Leading Technology Research
Project via grant 2015AA015409.

## References

  * Bird et al. (2009) Bird, Steven, Edward Loper, and Ewan Klein. 2009.  Natural Language Processing with Python.  O’Reilly Media Inc.
  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading wikipedia to answer open-domain questions.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pages 1870–1879.  https://doi.org/10.18653/v1/P17-1171.
  * Chollet (2015) François Chollet. 2015.  Keras.  https://github.com/fchollet/keras.
  * Cui et al. (2017) Yiming Cui, Zhipeng Chen, Si Wei, Shijin Wang, Ting Liu, and Guoping Hu. 2017.  Attention-over-attention neural networks for reading comprehension.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pages 593–602.  https://doi.org/10.18653/v1/P17-1055.
  * Cui et al. (2018) Yiming Cui, Ting Liu, Zhipeng Chen, Wentao Ma, Shijin Wang, and Guoping Hu. 2018\.  Dataset for the first evaluation on chinese machine reading comprehension.  In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018). European Language Resources Association (ELRA).
  * Cui et al. (2016) Yiming Cui, Ting Liu, Zhipeng Chen, Shijin Wang, and Guoping Hu. 2016.  Consensus attention-based neural networks for chinese reading comprehension.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers. Osaka, Japan, pages 1777–1786.
  * Graves and Schmidhuber (2005) Alex Graves and Jürgen Schmidhuber. 2005.  Framewise phoneme classification with bidirectional lstm and other neural network architectures.  Neural Networks 18(5-6):602–610.
  * Hermann et al. (2015) Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend.  In Advances in Neural Information Processing Systems. pages 1684–1692.
  * Hill et al. (2015) Felix Hill, Antoine Bordes, Sumit Chopra, and Jason Weston. 2015.  The goldilocks principle: Reading children’s books with explicit memory representations.  arXiv preprint arXiv:1511.02301 .
  * Ostermann et al. (2018) Simon Ostermann, Michael Roth, Ashutosh Modi, Stefan Thater, and Manfred Pinkal. 2018.  SemEval-2018 Task 11: Machine Comprehension using Commonsense Knowledge.  In Proceedings of International Workshop on Semantic Evaluation (SemEval-2018). New Orleans, LA, USA.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, pages 1532–1543.  http://aclweb.org/anthology/D14-1162.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, pages 2383–2392.  https://doi.org/10.18653/v1/D16-1264.
  * Srivastava et al. (2015) Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. 2015.  Highway networks.  arXiv preprint arXiv:1505.00387 .
  * Theano Development Team (2016) Theano Development Team. 2016.  Theano: A Python framework for fast computation of mathematical expressions.  arXiv e-prints abs/1605.02688.  http://arxiv.org/abs/1605.02688.


# Some inequalities for norms in $\mathbb{R}^{n}$ and $\mathbb{C}^{n}$

Stefan Gerdjikov  S. Gerdjikov
Faculty of Mathematics and Informatics
Sofia University
James Bourchier Blvd. 5, 1164 Sofia, Bulgaria

Institute for Information and Communication Technologies

Bulgarian Academy of Sciences
Acad. G. Bonchev 2, 1113 Sofia, Bulgaria  and  Nikolai Nikolov  N. Nikolov
Institute of Mathematics and Informatics
Bulgarian Academy of Sciences
Acad. G. Bonchev 8, 1113 Sofia, Bulgaria
Faculty of Information Sciences
State University of Library Studies and Information Technologies
Shipchenski prohod 69A, 1574 Sofia, Bulgaria<EMAIL_ADDRESS>
###### Abstract.

The main result of this paper is that for any norm on a complex or real
$n$-dimensional linear space, every extremal basis satisfies inverted triangle
inequality with scaling factor $2^{n}-1$. Furthermore, the constant $2^{n}-1$
is tight. We also prove that the norms of any two extremal bases are
comparable with a factor of $2^{n}-1$, which, intuitively, means that any two
extremal bases are quantitatively equivalent with the stated tolerance.

###### Key words and phrases:

norm, convex domain

###### 2010 Mathematics Subject Classification:

52A40, 52A21, 32F17

The second named author was partially supported by the Bulgarian National
Science Fund, Ministry of Education and Science of Bulgaria under contract
KP-06-N52/3.

##  1\. Introduction

_Extremal bases_ , originally introduced in [7, 3], have been established as a
useful tool in the study of the properties of the so called
$\mathbb{C}$-convex domains, $D$. On the one hand side they induce a natural
orthonormal coordinate system around any given point $z$ in the interior of
the domain $D$. On the other hand, under certain assumptions, see below, every
extremal basis $B$ at point $z$ enjoys the following inequalities:

(1) $\left(\sum_{b\in
B}\frac{|\left<{b,v}\right>|}{d_{D}(z;b)}\right)^{-1}\lesssim
d_{D}(z;v)\lesssim\left(\sum_{b\in
B}\frac{|\left<{b,v}\right>|}{d_{D}(z;b)}\right)^{-1},$

where $d_{D}(z;v)$ corresponds to the distance from $z$ to the boundary of $D$
in direction $v$, i.e.:

$d_{D}(z;v)=\sup\\{r\in\mathbb{R}^{+}|\ z+\lambda v\in D\text{ whenever
}|\lambda|<r\\}.$

This means that the extremal bases provide a convenient linear approximation
of the structure of the body $D$ in a neighbourhood of any given point $z$ in
the interior of the body.

The property 1 of extremal bases has facilitated the construction of
plurisubharmonic functions with bounded Hessians and for obtaining of
estimates for the Bergman kernels, [7, 8]. In [3, 4], the author states and
uses the estimates 1 to obtain Hölder and $L^{p}$ estimates for the solutions
of Cauchy-Riemann equations on smooth bounded pseudoconvex domains $D$ of
finite type. Estimates 1 have been also applied in the study of the Kobayashi
and Bergman metrics, [7, 9, 11, 10] and more recently, [12]. For a survey on
the geometry of extremal bases and their applications we refer to [2].

The construction of maximal bases can be described as a greedy procedure. One
starts with an arbitrary point $z$ in the interior of a $\mathbb{C}$-convex
domain $D$ and an empty set of vectors/directions $B_{0}$. Next, inductively,
the current set $B_{k}$ is extended to $B_{k+1}$ by adding an _extremal_
direction $v_{k+1}$ that is orthogonal to the subspace spanned by $B_{k}$. The
process terminates once the set $B:=B_{n}$ spans the entire space in which
case $B$ is the desired basis.

The notion of _extremity_ can be specified as _maximal_ , [7, 8], or as
_minimal_ , [3, 4], and the difference consists in whether one selects:

$\displaystyle v_{k+1}$ $\displaystyle\in$
$\displaystyle\arg\max\\{d_{D}(z;v)\,|\,v\perp span(B_{k})\\}\text{ or }$
$\displaystyle v_{k+1}$ $\displaystyle\in$
$\displaystyle\arg\min\\{d_{D}(z;v)\,|\,v\perp span(B_{k})\\}.$

Though important for the applications, the proofs of the estimates 1 departing
from geometric or analytical view points, depend on some kind of smoothness
conditions for the domain $D$, [7, 8, 10], and often provide only implicit or
rough estimates for the hidden constant. In particular, it is not evident if
and how it depends on the domain $D$.

In this paper, we give answer to the above questions by proving that the
estimates 1 are valid with constant $2^{n}-1$ where $n$ is the dimensionality
of the space in which the (so called weakly linear) convex domain $D$ resides.
In this sense this constant is independent of $D$. Furthermore it turns out
that the constant $2^{n}-1$ is sharp, that is it cannot be improved.

Our approach is algebraic. It departs from the observation that for a weakly
linear convex domain $D$ and any particular point $z$ in the interior of $D$,
the function:

$f(v)=\frac{1}{d_{D}(z;v)}$

is a semi-norm. If further the domain $D$ does not contain complex lines, then
$f$ is a norm, but see Remark 1 which suggests that this assumption is not
essential and it is only for technical reasons that we restrict our
considerations to norms. Thus the estimates 1 can be restated as:

(2) $\sum_{b\in B}|\left<{b,v}\right>|f(b)\gtrsim f(v)\gtrsim\sum_{b\in
B}|\left<{b,v}\right>|f(b)$

and wheres the first inequality is satisfied with constant $1$, as it easily
follows by the triangle inequality, the second inequality seems to be more
challenging.

To keep the outline self-contained, in Section 2 we prove that every (bounded
on the unit sphere) norm can be represented as:

$f(v)=\sup_{u\in U}|\left<{v,u}\right>|$

for an appropriate set of vectors $U$. The geometric interpretation of $U$ is
that the vectors $u\in U$ define the supporting hyperplanes to the body $D$
centred at $z$.

In Section 3 we state and prove that for any extremal basis $B$:

$(2^{n}-1)f(v)\geq\sum_{b\in B}|\left<{b,v}\right>|f(b).$

We should stress that the definition of maximal and minimal in our notation,
see Definition 2, are reciprocal to the notions used for bodies. The reason is
that maximising $d_{D}(z;.)$ is equivalent to minimising $f$ and vice versa.
Thus, Theorem 4 proves the statement for maximal bases w.r.t. $d_{D}(z;.)$ and
for minimal bases w.r.t. $f$, whereas Theorem 5 proves the statement for
minimal bases w.r.t. $d_{D}(z;.)$ and maximal bases w.r.t. $f$.

In Section 3 we prove that $2^{n}-1$ is the best possible bound. Namely, we
show that for every $\varepsilon>0$ there are norms whose maximal, resp.
minimal, bases violate the inequality:

$(2^{n}-1-\varepsilon)f(v)\geq\sum_{b\in B}|\left<{b,v}\right>|f(b)$

for at least one vector $v$. Since every norm gives rise to a convex body
$D^{\prime}=\\{v\,|\,f(v)\leq 1\\}$ such that
$d_{D^{\prime}}(0;v)=\frac{1}{f(v)}$, the results translate immediately for
convex bodies. Again, Proposition 6 handles the case of maximal basis w.r.t.
$d_{D}(z;.)$ and minimal basis w.r.t. $f$, whereas Proposition 7 handles the
case of minimal basis w.r.t. $d_{D}(z;.)$ and maximal basis w.r.t. $f$.

In Section 5 we show that minimal and maximal bases are equivalent in their
norms. Whereas similar result has been previously proven in [10], the bounds
in Section 5 are based on more accurate analysis of the algebraic structure
and improve the estimate fo the constants from $2^{n}n!$ to $2^{n}$, thus
reducing a factor of $n!$.

We conclude in Section 6 with some open problems.

##  2\. Preliminaries

In what follows we assume that $V$ is a linear space on
$\mathbb{F}=\mathbb{R}$ or $\mathbb{F}=\mathbb{C}$ and that $V$ is supplied
with a scalar product $\left<{\cdot,\cdot}\right>:V\times
V\rightarrow\mathbb{F}$. We denote with $\|.\|:V\rightarrow\mathbb{R}^{+}$ and
$\mathbb{S}_{1}$ the induced norm and the unit sphere in $V$, respectively,
i.e.:

$\displaystyle\|u\|$ $\displaystyle=$ $\displaystyle\left<{u,u}\right>\text{
for }u\in V$ $\displaystyle\mathbb{S}_{1}$ $\displaystyle=$
$\displaystyle\\{u\in V\,|\,\left<{u,u}\right>=1\\}.$

######  Lemma 1.

Let $f:V\rightarrow\mathbb{R}^{+}$ be a norm. Assume that $f$ is bounded on
the unit sphere $\mathbb{S}_{1}\subset V$.

  1. (1)

There is a set of vectors $U\subseteq V$ such that:

$f(v)=\sup_{u\in U}|\left<{v,u}\right>|.$

  2. (2)

If $v_{0}\in V$ is a unit vector such that
$f(v_{0})=\sup_{v\in\mathbb{S}_{1}}f(v)$, then for all $u\in V$ it holds that:

$f(u)\geq|\left<{v,u}\right>|f(v).$

###### Proof.

  1. (1)

The first part is an immediate consequence of Hahn-Banach Theorem. Indeed, let
$v\in V$. Then denoting by $V_{0}=span(v)$, we define
$L_{0}:V_{0}\rightarrow\mathbb{F}$ as $L_{0}(\alpha v)=\alpha f(v)$. Clearly,
$L_{0}$ is a linear functional on $V_{0}$ and $|L_{0}(\alpha
v)|=|\alpha|f(v)=f(\alpha v)$. By Hanh-Banach Theorem, since $f$ is a norm, we
can extend $L_{0}$ to a linear functional $L_{v}:V\rightarrow\mathbb{F}$ such
that $|L_{v}(u)|\leq f(u)$ for all $u\in V$. Since $L_{v}$ is linear on $V$
and $\sup_{u\in\mathbb{S}_{1}}L_{v}(u)$ is bounded above by
$\sup_{u\in\mathbb{S}_{1}}f(u)<\infty$, it follows that $L_{v}$ is a bounded
linear operator and cosequently there is a vector $v^{*}\in V$ such that:

$\left<{u,v^{*}}\right>=L_{v}(u)\text{ for all }u\in V.$

Let $U=\\{v^{*}\,|\,v\in V\\}$. It is straightforward that for any $u\in V$
and $v^{*}\in U$, $|\left<{u,v^{*}}\right>|=|L_{v}(u)|\leq f(u)$. On the other
hand $f(u)=L_{u}(u)=|\left<{u,u^{*}}\right>|$. Therefore:

$f(v)=\sup_{u\in U}|\left<{v,u}\right>|.$

  2. (2)

For the second part, consider the linear functional $L=L_{v_{0}}$ induced by
$v_{0}$. Since $L$ is linear, it is determined by its values on an orthonormal
basis on $V$. Without loss of generality we may and we do assume that
$(e_{i})_{i\in I}$ is such a basis with $e_{1}=v_{0}$. Assume that
$L(e_{i})\neq 0$ for some $i>1$. Then we consider the vector:

$u=\overline{L(e_{1})}v_{0}+\overline{L(e_{i})}e_{i}=f(v_{0})v_{0}+\overline{L(e_{i})}e_{i}.$

Then we have that $\|u\|=\sqrt{f^{2}(v_{0})+|L(e_{i})|^{2}}$ and:

$L(u)=f(v_{0})L(v_{0})+\overline{L(e_{i})}L(e_{i})=f(v_{0})^{2}+|L(e_{i})|^{2}.$

Hence $u^{\prime}=\frac{u}{\|u\|}$ is a unit vector and
$L(u^{\prime})=\sqrt{f(v_{0})^{2}+|L(e_{i})|^{2}}$ implying that
$L(u^{\prime})>f(v_{0})$ since $L(e_{i})\neq 0$. However, $f(u^{\prime})\geq
L(u^{\prime})>f(v_{0})$ and this contradicts the maximality of $v_{0}$.
Consequently, $L(e_{i})=0$ for any $i\neq 1$. This proves that
$L(u)=\left<{u,e_{1}}\right>L(e_{1})=\left<{u,v_{0}}\right>f(v_{0})$ and
therefore:

$|\left<{u,v_{0}}\right>|f(v_{0})=|L(u)|\leq f(u)$

as required.

∎

######  Remark 1.

We can view the first part of the above lemma as a characterisation of
(semi)norms. Indeed, if $U\subseteq V$, then
$f_{U}:V\rightarrow\mathbb{R}^{+}$ defined as:

$f_{U}(v)=\sup_{u\in U}|\left<{v,u}\right>|$

is a semi-norm. Actually, it is a norm iff $U^{\perp}=\\{v\in V\,|\,\forall
u\in U(\left<{u,v}\right>=0)\\}$ is the trivial set $\\{0\\}$. Since,
$U^{\perp}$ is a subspace of $V$, the properties of $f_{U}$ are uniquely
determined by the behaviour of $f_{U}$ on the orthogonal subspace of
$U^{\perp}$. Indeed, if $v=v^{\prime}+u$ with $u\in U^{\perp}$ and
$v^{\prime}\perp U^{\perp}$ then:

$f_{U}(v^{\prime})\leq f_{U}(v)+f_{U}(u)=f(v)\text{ and }f_{U}(v)\leq
f_{U}(v^{\prime})+f_{U}(-u)=f_{U}(v^{\prime}),$

that is $f_{U}(v^{\prime})=f_{U}(v)$.

##  3\. Minimal and Maximal Bases

In this section we assume that $n$ is a positive integer, and $V$ is an
$n$-dimensional linear space supplied with a scalar product
$\left<{\cdot,\cdot}\right>:V\times V\rightarrow\mathbb{F}$ where
$\mathbb{F}\in\\{\mathbb{R},\mathbb{C}\\}$.

######  Definition 2.

Let $f:V\rightarrow\mathbb{R}^{+}$ be a norm. We define an _$f$ -minimal
($f$-maximal, resp.)_ (orthonormal) basis for $V$ inductively as follows:

  * •

$n=1$, then for any $b\in\mathbb{S}_{1}$, $(b)$ is an $f$-minimal
($f$-maximal, resp.) basis.

  * •

$n>1$, then let:

$\displaystyle b_{1}$ $\displaystyle\in$
$\displaystyle\arg\min\\{f(b)\,|\,b\in\mathbb{S}_{1}\\}(b_{1}\in\arg\max\\{f(b)\,|\,b\in\mathbb{S}_{1}\\},\text{
resp.})$ $\displaystyle V_{1}$ $\displaystyle=$ $\displaystyle\\{u\in
V\,|\,\left<{u,v}\right>=0\\}$ $\displaystyle f_{1}$ $\displaystyle=$
$\displaystyle f\upharpoonright V_{1}\text{ be the restriction of }f\text{ to
}V_{1}.$

If $(b_{2},b_{3},\dots,b_{n})$ is an $f_{1}$-minimal ($f_{1}$-maximal, resp.)
basis for $V_{1}$, then $(b_{1},b_{2},\dots,b_{n})$ is an $f$-minimal
($f$-maximal, resp.) basis for $V$.

######  Definition 3.

We say that two orthonormal bases $(b_{1},\dots,b_{n})$ and
$(e_{1},\dots,e_{n})$ of $V$ are _equivalent_ if for every $i\leq n$ $b_{i}$
and $e_{i}$ are collinear, i.e. there is an element $\alpha_{i}\in\mathbb{F}$
with $|\alpha_{i}|=1$ such that $e_{i}=\alpha_{i}b_{i}$.

######  Theorem 4.

For any norm $f:V\rightarrow\mathbb{R}^{+}$ and any $f$-minimal basis
$(b_{1},b_{2},\dots,b_{n})$ it holds that:

$(2^{n}-1)f(v)\geq\sum_{i=1}^{n}|\left<{v,b_{i}}\right>|f(b_{i}).$

###### Proof.

First note that for any $v\in V$ there are unique $\alpha\in\mathbb{F}$ and
vector $u\in span(b_{2},\dots,b_{n})$ such that:

$v=u+\alpha b_{1}.$

The statement being obvious for $v=0$, we assume that $v\neq 0$ and set
$v^{\prime}=\frac{v}{\|v\|}$. Then $v^{\prime}\in\mathbb{S}_{1}$ and by the
definition of $b_{1}$, we get that:

$f(v^{\prime})\geq
f(b_{1})\geq\frac{|\left<{v,b_{1}}\right>|}{\|v\|}f(b_{1})=\frac{|\alpha|}{\|v\|}f(b_{1}),$

where we used the Cauchy-Schwartz inequality. So far we have that:

$f(v)=\|v\|f(v^{\prime})\geq|\alpha|f(b_{1}).$

This settles the case where $n=1$. Alternatively, i.e. for $n\geq 2$, we use
the triangle inequality for $u=v-\alpha b_{1}$ to conclude that:

$f(u)=f(v-\alpha b_{1})\leq f(v)+|\alpha|f(b_{1})\leq f(v)+f(v)=2f(v).$

With this inequality at hand we can conclude the proof the by induction on
$n$. As we noticed, the case $n=1$ is settled. Assume that the conclusion of
the lemma holds for any $(n-1)$-dimensional vector space $V^{\prime}$ and
consider the vector space $V$ of dimension $n$. Let
$V^{\prime}=span(b_{2},\dots,b_{n})$ and $f^{\prime}=f\upharpoonright
V^{\prime}$. It follows, by definition, that $(b_{2},\dots,b_{n})$ is an
$f^{\prime}$-minimal basis for $V^{\prime}$ and therefore by the induction
hypothesis:

$(2^{n-1}-1)f^{\prime}(u)\geq\sum_{i=2}^{n}|\left<{u,b_{i}}\right>|f(b_{i})\text{
for any }u\in V^{\prime}.$

Finally, for any non-zero $v=u+\alpha b_{1}$ with $\alpha\in\mathbb{F}$ and
$u\in V^{\prime}$ we have proven that:

$f(v)\geq 2f(u)=2f(u^{\prime})\text{ and }f(v)\geq|\alpha|f(b_{1}).$

Summing up, and using that $\left<{v,b_{i}}\right>=\left<{u,b_{i}}\right>$ for
$i\geq 2$, we conclude that:

$\displaystyle(2^{n}-1)f(v)$ $\displaystyle=$ $\displaystyle
2(2^{n-1}-1)f(v)+f(v)$ $\displaystyle\geq$
$\displaystyle(2^{n-1}-1)f(u)+|\alpha|f(b_{1})$ $\displaystyle\geq$
$\displaystyle|\alpha|f(b_{1})+\sum_{i=2}^{n}|\left<{u,b_{i}}\right>|f(b_{i})$
$\displaystyle=$
$\displaystyle|\left<{v,b_{1}}\right>|f(b_{1})+\sum_{i=2}^{n}|\left<{v,b_{i}}\right>|f(b_{i})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}|\left<{v,b_{i}}\right>|f(b_{i}).$

∎

######  Theorem 5.

For any norm $f:V\rightarrow\mathbb{R}^{+}$ and any $f$-maximal basis
$(b_{1},b_{2},\dots,b_{n})$ it holds that:

$(2^{n}-1)f(v)\geq\sum_{i=1}^{n}|\left<{v,b_{i}}\right>|f(b_{i}).$

###### Proof.

We proceed by induction on $n=dimV$. For $n=1$ there is nothing to prove.
Assume that the statement of the lemma holds for vector spaces with
dimensionality $n$. Let $f:V\rightarrow\mathbb{R}^{+}$ be a norm. Since
$f(b_{1})=\max_{v\in\mathbb{S}_{1}}f(v)$, by Lemma 1 we have that:

$f(u)\geq|\left<{u,b_{1}}\right>|f(b_{1}).$

Let $V_{1}=span(b_{2},\dots,b_{n})$ and consider an arbitrary vector $u=\alpha
b_{1}+v$ with $v\in V_{1}$. Then, we have:

$f(u)\geq|\alpha|f(b_{1}).$

Furthermore, by the triangle inequality we have:

$f(u)+|\alpha|f(b_{1})=f(\alpha b_{1}+v)+f(-\alpha b_{1})\geq f(v).$

Summing up we obtain that $2f(u)\geq f(u)+|\alpha|f(b_{1})\geq f(v)$. To
complete the inductive step, we use that
$\left<{u,b_{i}}\right>=\left<{v,b_{i}}\right>$ for $i\geq 2$ and the
inductive hypothesis for $V_{1}$ and $f_{1}=f\upharpoonright V_{1}$. Thus, we
compute:

$\displaystyle(2^{n}-1)f(u)$ $\displaystyle\geq$ $\displaystyle
f(u)+2(2^{n-1}-1)f(u)$ $\displaystyle\geq$
$\displaystyle|\alpha|f(b_{1})+(2^{n-1}-1)f(v)$ $\displaystyle\geq$
$\displaystyle|\alpha|f(b_{1})+\sum_{i=2}^{n}|\left<{v,b_{i}}\right>|f(b_{i})$
$\displaystyle=$
$\displaystyle|\alpha|f(b_{1})+\sum_{i=2}^{n}|\left<{u,b_{i}}\right>|f(b_{i})$

where the second line follows by the fact $f(u)\geq|\alpha|f(b_{1})$ and
$2f(u)\geq f(v)$, and the third line follows by the inductive hypothesis. ∎

##  4\. Lower Bounds

In this section we prove that the results from Theorems 4 and 5 are sharp. Our
constructions use the characterisation from Lemma 1 and Remark 1 as a basic
tool to define norms. In both cases given an $\varepsilon>0$, we construct a
finite set $U\subseteq\mathbb{R}^{n}$ that defines a norm:

$f:\mathbb{C}^{n}\rightarrow\mathbb{R}^{+}\text{ s.t. }f(v)=\max_{u\in
U}|\left<{v,u}\right>|.$

The set $U$ is tailored in such a way that it admits:

  1. (1)

as $f$-minimal ($f$-maximal, resp.) an orthonormal111Actually, it is unique up
to equivalence. basis

$(e_{1},\dots,e_{n})\subset\mathbb{R}^{n}$

and

  2. (2)

a witness $v_{0}\in\mathbb{R}^{n}$ such that:

$(2^{n}-1-\varepsilon)f(v_{0})<\sum_{i=1}^{n}|\left<{v_{0},e_{i}}\right>|f(e_{i}).$

Since $U\subseteq\mathbb{R}^{n}$, $(e_{1},\dots,e_{n})\subseteq\mathbb{R}^{n}$
and $v_{0}\in\mathbb{R}^{n}$, the restriction $f_{R}$ of $f$ to
$\mathbb{R}^{n}$ provides a norm:

$f_{R}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{+}\text{ with }f_{R}(v)=f(v)$

that admits as $f_{R}$-minimal ($f$-maximal, resp.) basis again
$(e_{1},\dots,e_{n})$ and $v_{0}$ is a witnesses that:

$(2^{n}-1-\varepsilon)f_{R}(v_{0})<\sum_{i=1}^{n}|\left<{v_{0},e_{i}}\right>|f_{R}(e_{i}).$

######  Proposition 6.

Let $n\geq 1$be an integer and $V=\mathbb{C}^{n}$. Then for any
$\varepsilon>0$, there is a norm $f:V\rightarrow\mathbb{R}^{+}$ and a nonzero
vector $v\in\mathbb{R}^{n}$ such that:

  1. (1)

$f$ admits a unique, up to equivalence, $f$-minimal basis

$(e_{1},\dots,e_{n})\subseteq\mathbb{R}^{n}$

and

  2. (2)

$(2^{n}-1-\varepsilon)f(v)\leq\sum_{i=1}^{n}|\left<{v,e_{i}}\right>|f(e_{i}).$

###### Proof.

Let $(e_{1},e_{2},\dots,e_{n})\subseteq\mathbb{R}^{n}$ be a fixed orthonormal
basis for $V$ and $\varepsilon>0$. We set $V_{i}=span(e_{i},\dots,e_{n})$.
Finally, let $s\in(0,1)$ whose value will be specified appropriately later. We
set out to inductively construct sets $U_{i}\subseteq
V_{i}\cap\mathbb{R}^{n}$, norms $f_{i}:V_{i}\rightarrow\mathbb{R}^{+}$ and
witnesses $v^{(i)}\in V_{i}\cap\mathbb{R}^{n}$ with the following properties:

  1. (1)

$f_{i}(v)=\max\\{|\left<{v,u}\right>|\,|\,u\in U_{i}\\}$,

  2. (2)

$f_{i}(e_{i})=1=\min_{v\in\mathbb{S}_{1}\cap V_{i}}f_{i}(v)$,

  3. (3)

$f_{i}(v)=\frac{1}{s^{2}(2s+1)}f_{i+1}(v)$ for all $v\in V_{i+1}$,

  4. (4)

$\left<{v^{(i)},e_{j}}\right>=(2s^{2})^{j-i}$ is such that
$f_{i}(v^{(i)})\in[1,1+2s)$ and:

$(2^{n-i}-1)f(v^{(i)})<\sum_{j=i}^{n}|\left<{v^{(i)},e_{j}}\right>|(1+2s)^{2(j-i)+1}f_{i}(e_{j}))$

We start with $U_{n}=\\{e_{n}\\}$ and $f_{n}(\alpha e_{n})=|\alpha|$,
$v^{(n)}=e_{n}$. It is straightforward to see that these objects satisfy the
above assumptions. Assume that for some $i>1$ the set $U_{i}$, the norm
$f_{i}$ and the witness $v^{(i)}$ are defined and satisfy the above
assumptions. We define $U_{i-1}$, $f_{i-1}$ and $v^{(i-1)}$ as follows. Let

$U_{i}^{+}=\\{u\in U_{i}\,|\,\left<{v^{(i)},u}\right>\geq 0\\}\text{ and
}U_{i}^{-}=\\{u\in U_{i}\,|\,\left<{v^{(i)},u}\right><0\\}.$

Next we define:

$\displaystyle U_{i-1}$
$\displaystyle=\left\\{e_{i-1}+\frac{1}{s(2s+1)}u\,|\,u\in
U^{+}_{i}\right\\}\cup\left\\{e_{i-1}-\frac{1}{s^{2}(2s+1)}u\,|\,u\in
U^{+}_{i}\right\\}$
$\displaystyle\cup\left\\{e_{i-1}-\frac{1}{s(2s+1)}u\,|\,u\in
U^{-}_{i}\right\\}\cup\left\\{e_{i-1}+\frac{1}{s^{2}(2s+1)}u\,|\,u\in
U^{-}_{i}\right\\}.$

Now, we define $f_{i-1}$ and $v_{i-1}$ as:

$\displaystyle f_{i-1}$ $\displaystyle=$
$\displaystyle\max\\{|\left<{v,u}\right>|\,|\,u\in U_{i-1}\\}$ $\displaystyle
v^{(i-1)}$ $\displaystyle=$ $\displaystyle e_{i-1}+2s^{2}v^{(i)}.$

Note that since, by assumption, $U_{i}\subseteq\mathbb{R}^{n}$ and
$v^{(i)}\in\mathbb{R}^{n}$, the sets $U_{i}^{+}$ and $U_{i}^{-}$ are well-
defined. Hence, it should be clear that the $U_{i-1}\subseteq\mathbb{R}^{n}$
and $v^{(i-1)}\in\mathbb{R}^{n}$.

Now we verify that $U_{i-1}$, $f_{i-1}$ and $v^{(i-1)}$ possess the desired
properties:

  1. (1)

The first property is satisfied by definition.

  2. (2)

The third property is also clear for $s\in(0,1)$.

  3. (3)

To see that the second property holds, first note that:

$\left<{e_{i-1},u}\right>=1\text{ for all }u\in U_{i-1}.$

Next, consider an arbitrary element $v\in U_{i-1}\cap\mathbb{S}_{1}$. It has a
unique representation $v=\alpha e_{i-1}+v^{\prime}$ with
$|\alpha|^{2}+\|v^{\prime}\|^{2}=1$ with $v^{\prime}\in V_{i}$. By the
induction hypothesis we have that $f_{i}(v^{\prime})\geq\|v^{\prime}\|$. Since
$U_{i}$ is finite, the value
$f_{i}(v^{\prime})=|\left<{v^{\prime},u^{\prime}}\right>|$ is attained for
some $u^{\prime}\in U_{i}$. Let us fix such $u^{\prime}$ and set
$a,b\in\mathbb{R}$ such that:

$\left<{v^{\prime},u^{\prime}}\right>=a+ib.$

We also set $c,d\in\mathbb{R}$ such that $\alpha=c+id$. Thus, for if
$\sigma\in\\{s^{-1},s^{-2},-s^{-1},-s^{-2}\\}$ we have:

$\left<{v,e_{i-1}+\sigma u^{\prime}}\right>=c+id+\sigma(a+ib)=(c+\sigma
a)+i(d+\sigma b).$

Consequently:

$\displaystyle|\left<{v,e_{i-1}+\sigma u^{\prime}}\right>|$ $\displaystyle=$
$\displaystyle(c+\sigma a)^{2}+(d+\sigma b)^{2}$ $\displaystyle=$
$\displaystyle c^{2}+d^{2}+\sigma^{2}(a^{2}+b^{2})+2\sigma(ac+bd)$
$\displaystyle=$
$\displaystyle|\alpha|^{2}+\sigma^{2}|\left<{v^{\prime},u^{\prime}}\right>|^{2}+2\sigma(ac+bd)$
$\displaystyle=$
$\displaystyle|\alpha|^{2}+\sigma^{2}f^{2}_{i}(v^{\prime})+2\sigma(ac+bd)$
$\displaystyle\geq$
$\displaystyle|\alpha|^{2}+\sigma^{2}\|v^{\prime}\|^{2}+2\sigma(ac+bd).$

By construction, we can always choose the sign of $\sigma$, i.e. we have
either the option $\sigma\in\\{s^{-1},-s^{-2}\\}$ or
$\sigma\in\\{-s^{-1},s^{-2}\\}$. Now, choosing $\sigma$ such that the sign of
$\sigma$ is the same as $(ac+bd)$ we conclude that:

$\displaystyle|\left<{v,e_{i-1}+\sigma u^{\prime}}\right>|$
$\displaystyle\geq$
$\displaystyle|\alpha|^{2}+\sigma^{2}\|v^{\prime}\|^{2}+2\sigma(ac+bd)$
$\displaystyle\geq$ $\displaystyle|\alpha|^{2}+\sigma^{2}\|v\|^{2}$
$\displaystyle\geq$ $\displaystyle|\alpha|^{2}+\|v^{\prime}\|^{2}$
$\displaystyle=$ $\displaystyle 1,$

where the first inequality follows by the choice of $\sigma$ and the second by
the fact that $|\sigma|>1$. Furthermore the last inequality turns into
equality if and only if $v^{\prime}=0$. This proves that for any vector
$v\in\mathbb{S}_{1}\cap V_{i-1}$ which is not collinear with $e_{i-1}$, it
holds that $f_{i}(v)>1$. Consequently:

$f_{i-1}(e_{i-1})=\min_{v\in V_{i-1}\cap\mathbb{S}_{1}}f_{i-1}(v)$

and the minimum is attained only for vectors of the form $\alpha e_{i-1}$ with
$|\alpha|=1$. Hence w.l.o.g. $e_{1}$ belongs to the minimal basis.

  4. (4)

Finally, we check the last condition. Let $v^{(i-1)}\in V_{i-1}$ be such that:

$v^{(i-1)}=e_{i-1}+2s^{2}v^{(i)}.$

First, let $u\in U_{i}^{+}$. In particular, $\left<{u,v^{(i)}}\right>\geq 0$.
Therefore:

$\displaystyle\left<{v^{(i-1)},e_{i-1}-\frac{1}{s^{2}(2s+1)}u}\right>$
$\displaystyle=$
$\displaystyle\left<{e_{i-1}+2s^{2}v^{(i)},e_{i-1}-\frac{1}{s^{2}(2s+1)}u}\right>$
$\displaystyle=$ $\displaystyle
1-\frac{2}{2s+1}\left<{v^{(i)},u^{\prime}}\right>$ $\displaystyle=$
$\displaystyle 1-\frac{2}{2s+1}|\left<{v^{(i)},u}\right>|\leq 1.$

Since $u\in U_{i}$, we have that
$f_{i}(v^{(i)})\geq|\left<{v^{(i)},u}\right>|$ and by the assumption that
$f_{i}(v^{(i)})\leq 1+2s$ we conclude that:

$\left<{v^{(i-1)},e_{i-1}-\frac{1}{s^{2}(2s+1)}u}\right>=1-\frac{2}{2s+1}|\left<{v^{(i)},u}\right>|>1-2=-1.$

Hence $|\left<{v^{(i-1)},e_{i-1}-\frac{1}{s^{2}(2s+1)}u}\right>|\leq 1$ for
all $u\in U_{i}^{+}$. On the other hand:

$\displaystyle\left<{v^{(i-1)},e_{i-1}+\frac{1}{s(2s+1)}u}\right>$
$\displaystyle=$ $\displaystyle
1+\frac{2s^{2}}{s(2s+1)}\left<{v^{(i)},u}\right>$ $\displaystyle=$
$\displaystyle 1+\frac{2s}{1+2s}|\left<{v^{(i)},u}\right>|\in[1,1+2s).$

Similarly, for $u\in U_{i}^{-}$ we have that:

$\displaystyle\left<{v^{(i-1)},e_{i-1}+\frac{1}{s^{2}(2s+1)}u}\right>$
$\displaystyle=$ $\displaystyle
1-\frac{2}{2s+1}|\left<{v^{(i)},u}\right>|\in(-1,1]$
$\displaystyle\left<{v^{(i-1)},e_{i-1}-\frac{1}{s(2s+1)}u}\right>$
$\displaystyle=$ $\displaystyle
1+\frac{2s}{2s+1}|\left<{v^{(i)},u}\right>|\in[1,1+2s).$

Hence the maximum value of $\left<{v^{(i-1)},u^{\prime}}\right>$ when
$u^{\prime}\in U_{i-1}$ is attained for some $u^{\prime}$ of the form

$\displaystyle u^{\prime}$ $\displaystyle=$ $\displaystyle
e_{i-1}+\frac{1}{s(2s+1)}u\text{ with }u\in U_{i}^{+}\text{ or}$
$\displaystyle u^{\prime}$ $\displaystyle=$ $\displaystyle
e_{i-1}-\frac{1}{s(2s+1)}u\text{ with }u\in U_{i}^{-}$

such that $|\left<{v^{(i)},u}\right>|$ is maximised. This shows that

$f_{i-1}(v^{(i-1)})=1+\frac{2s}{2s+1}f_{i}(v^{(i)}).$

So far we have that $f_{i-1}(v^{(i-1)})\in[1,1+2s)$.

We proceed to show that the last inequality holds, To this end, first note:

$\displaystyle\left<{v^{(i-1)},e_{i-1}}\right>$ $\displaystyle=$
$\displaystyle 1$ $\displaystyle\left<{v^{(i-1)},e_{j}}\right>$
$\displaystyle=$ $\displaystyle 2s^{2}\left<{v^{(i)},e_{j}}\right>\text{ for
}j\geq i.$

Recalling that $f_{i-1}(e_{i-1})=1$ and
$f_{i-1}(e_{j})=s^{2}(2s+1)f_{i}(e_{j})$ for $j\geq i$, we conclude that:

$(1+2s)|\left<{v^{(i-1)},e_{j}}\right>|f_{i-1}(e_{j})=2|\left<{v^{(i)},e_{j}}\right>|f_{i}(e_{j})\text{
for }j\geq i.$

Therefore, using that $f_{i-1}(v^{(i-1)})<1+2s\leq(1+2s)f_{i}(v^{(i)})$, we
compute:

$\displaystyle(2^{n-i+1}-1)f_{i-1}(v^{(i-1)})$ $\displaystyle=$ $\displaystyle
f_{i-1}(v^{(i-1)})+2(2^{n-i}-1)f_{i-1}(v^{(i-1)})$ $\displaystyle<$
$\displaystyle 1+2s+2(2^{n-i}-1)f_{i-1}(v^{(i-1)})$ $\displaystyle\leq$
$\displaystyle(1+2s)(1+2f_{i}(v^{(i)})(2^{n-i}-1))$ (inductive hypothesis)
$\displaystyle\leq$ $\displaystyle(1+2s)\left(1+\right.$
$\displaystyle\left.2\sum_{j=i}^{n}|\left<{v^{(i)},e_{j}}\right>|(1+2s)^{2(j-i)+1}f_{i}(e_{j})\right)$
$\displaystyle\leq$
$\displaystyle(1+2s)(|\left<{v^{(i-1)},e_{i-1}}\right>|f(e_{i-1})+$
$\displaystyle\sum_{j=i}^{n}(1+2s)^{2(j-i)+3}|\left<{v^{(i-1)},e_{j}}\right>|f_{i-1}(e_{j}))$
$\displaystyle(\text{ setting }i^{\prime}=i-1)$ $\displaystyle=$
$\displaystyle\sum_{j=i^{\prime}}^{n}(1+2s)^{2(j-i^{\prime})+1}|\left<{v^{(i^{\prime})},e_{j}}\right>|f_{i^{\prime}}(e_{j})$

as required.

Now letting $s$ tend to zero, we see that $f_{1}(v^{(1)})$ satisfies the
conclusion of the lemma. ∎

######  Proposition 7.

Let $n\geq 1$ be an integer and $V=\mathbb{C}^{n}$. For any real number
$\varepsilon>0$, there is a norm $f:V\rightarrow\mathbb{R}^{+}$ and a non-zero
vector $v\in\mathbb{R}^{n}$ such that:

  1. (1)

$f$ admits a unique up to equivalence $f$-maximal basis

$(e_{1},e_{2},\dots,e_{n})\subseteq\mathbb{R}^{n},$

  2. (2)

$(2^{n}-1-\varepsilon)f(v)<\sum_{i=1}^{n}|\left<{v,e_{i}}\right>|f(e_{i}).$

###### Proof.

Let $\varepsilon>0$ be fixed and $e_{1},\dots,e_{n}\in\mathbb{R}^{n}$ be an
orthonormal basis of $V$. We are going to construct a norm
$f:V\rightarrow\mathbb{R}^{+}$ whose unique $f$-maximal basis is
$(e_{1},\dots,e_{n})$ and satisfies the conclusion of the lemma. To this end
consider a real number $c\in(0,1)$ and an angle $\alpha\in(0,\pi)$ whose price
values will be determined appropriately.

Given, the constants $c$ and $\alpha$ we define the vector $u^{\prime}_{k}\in
V$ for $k=1,2\dots,n$ as follows:

$\displaystyle u^{\prime}_{1}$ $\displaystyle=$ $\displaystyle e_{1}$
$\displaystyle u^{\prime}_{k+1}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{k}e_{j}\sin^{j-1}\alpha\cos\alpha+e_{k+1}\sin^{k}\alpha.$

We set $u_{k}=c^{k-1}u_{k}^{\prime}$ and define the norm
$f:V\rightarrow\mathbb{R}^{+}$ as:

$f(v)=\sup\\{|\left<{v,u_{k}}\right>|\,|\,k\leq n\\}.$

By Remark 1 we know that $f$ is a semi-norm. Since
$f(e_{k})\geq|\left<{e_{k},u_{k}}\right>|>0$, we see, again by Remark 1, that
$f$ is a norm. Further, by Lemma 1, we know that the maximum value $f(v)$ on
$\mathbb{S}_{1}$ is attained at a vector that is collinear to some of the
vectors $u_{k}$ and is equal to $f(v)=\|u_{k}\|$. Since $\|u_{k}\|=c_{k}$, we
conclude that the first vector of the maximal basis is $e_{1}=u_{1}$. Next,
the subspace, $V_{1}$, of $V$ that is orthogonal to $e_{1}$ is spanned by
$(e_{2},\dots,e_{n})$ and therefore $f_{1}=f\upharpoonright V_{1}$ is
actually:

$f_{1}(v)=\sup\\{|\left<{v,u_{k}-u_{1}\cos\alpha}\right>\,|\,k\leq n\\}.$

Since $\|u_{k}-u_{1}\cos\alpha|=c^{k-1}\sin\alpha$, applying again Lemma 1, we
conclude that the maximal value of $f_{1}$ on $\mathbb{S}_{1}$ is attained at
$e_{2}$. Proceeding inductively, we may prove that $(e_{1},\dots,e_{n})$ is
the unique, up to equivalence, $f$-maximal basis. Note that:

$f(e_{i})=\left<{e_{i},u_{i}}\right>=c^{i-1}\sin^{i-1}\alpha.$

Let $w_{1}>0$ and $w_{i}=w_{1}\tg^{i-1}\frac{\alpha}{2}$. It should be clear
that:

$\displaystyle w_{i}\cos{\alpha}+w_{i+1}\sin{\alpha}$ $\displaystyle=$
$\displaystyle w_{i}(\cos{\alpha}+\sin{\alpha}\tg\frac{\alpha}{2})$
$\displaystyle=$ $\displaystyle
w_{i}(2\cos^{2}{\alpha/2}-1+2\sin^{2}{\alpha/2})=w_{i}.$

Therefore, setting $w=\sum_{i=1}^{n}w_{i}e_{i}$, we obtain that

$\left<{w,u_{k}}\right>=c^{k-1}\left<{w,u_{k}^{\prime}}\right>=c^{k-1}w_{1}$

and thus $|\left<{w,u_{k}}\right>|=c^{k-1}w_{1}\leq w_{1}$ with equality if
and only if $k=1$. Hence $f(w)=w_{1}$.

On the other hand:

$\displaystyle w_{i}f(e_{i})$ $\displaystyle=$ $\displaystyle
c^{i-1}w_{1}\tg^{i-1}\frac{\alpha}{2}\sin^{i-1}{\alpha}$ $\displaystyle=$
$\displaystyle c^{i-1}w_{1}\left(2\sin^{2}\frac{\alpha}{2}\right)^{i-1}$
$\displaystyle=$ $\displaystyle
2^{i-1}c^{i-1}w_{1}\sin^{(2(i-1))}\frac{\alpha}{2}.$

It follows that:

$\sum_{i=1}^{n}w_{i}f(e_{i})\geq
w_{1}\sum_{i=1}^{n}2^{i-1}[c^{i-1}\sin^{2(i-1)}\frac{\alpha}{2}].$

Clearly, letting $c$ tend to $1$ and $\alpha$ tend to $\pi-0$, the right hand
side tends to $w_{1}\sum_{i=1}^{n}2^{i-1}=(2^{n}-1)w_{1}=(2^{n}-1)f(w)$. Thus,
for any $\varepsilon>0$, we can find appropriate $c\in(0,1)$ and
$\alpha\in(0,\pi)$ such that
$(2^{n}-1-\varepsilon)f(w)<\sum_{i=1}^{n}w_{i}f(e_{i})$. ∎

##  5\. Equivalence of Bases

######  Definition 8.

Let $f:V\rightarrow\mathbb{R}^{+}$ be a norm. Let $(e_{1},e_{2},\dots,e_{n})$
be an orthonormal basis for $V$ arranged in increasing order w.r.t. $f$, i.e.:

$f(e_{1})\leq f(e_{2})\leq\dots\leq f(e_{n}).$

  1. (1)

For a constant $c\in\mathbb{R}^{+}$, we say that $(e_{1},e_{2},\dots,e_{n})$
satisfies the property $P_{f}(c)$ if for every
$\beta_{1},\beta_{2},\dots,\beta_{n}\in\mathbb{F}$ it holds:

$cf\left(\sum_{i=1}^{n}\beta_{i}e_{i}\right)\geq\sum_{i=1}^{n}|\beta_{i}|f(e_{i}).$

  2. (2)

More generally, for constants $c_{1},c_{2},\dots,c_{n}\in\mathbb{R}^{+}$, we
say that $(e_{1},\dots,e_{n})$ satisfies the property
$HP_{f}(c_{1},c_{2},\dots,c_{n})$ if for every $i$ and every
$\beta_{i},\beta_{i+1},\dots,\beta_{n}$ it holds that:

$c_{i}f\left(\sum_{j=i}^{n}\beta_{i}e_{i}\right)\geq\sum_{j=i}^{n}|\beta_{i}|f(e_{i}).$

######  Remark 2.

With these notions, Lemma 5 states that there is an $f$-maximal basis that
satisfies $P_{f}(2^{n}-1)$. Furthermore, since every prefix of an $f$-maximal
basis, $(b_{1},b_{2},\dots,b_{n})$, is a maximal basis for its linear span, it
follows that the $f$-maximal basis from Lemma 5 actually satisfies
$HP_{f}(2^{n}-1,2^{n-1}-1,\dots,1)$.

On the other hand, Lemma 4 states that every $f$-minimal basis satisfies
$P_{f}(2^{n}-1)$.

It is also obvious that if a basis $(e_{1},\dots,e_{n})$ satisfies $P_{f}(c)$,
then it satisfies $HP_{f}(c,c,\dots,c)$. Conversely, if an orthonormal basis
$(e_{1},\dots,e_{n})$ satisfies $HP_{f}(c_{1},\dots,c_{n})$, then it satisfies
$P_{f}(c_{1})$.

######  Lemma 9.

Let $(b_{1},b_{2},\dots,b_{n})$ and $(e_{1},e_{2},\dots,e_{n})$ be orthonormal
bases on $V$ and $f:V\rightarrow\mathbb{R}^{+}$ be a norm such that:

$\displaystyle f(b_{1})\leq f(b_{2})\leq\dots\leq f(b_{n})$ and $\displaystyle
f(e_{1})\leq f(e_{2})\leq\dots\leq f(e_{n}).$

Then:

  1. (1)

if $(b_{1},\dots,b_{n})$ is $f$-minimal, then for every $i\leq n$,
$f(b_{i})\leq\sqrt{i}f(e_{i})$,

  2. (2)

if $(e_{1},e_{2},\dots,e_{n})$ satisfies $HP_{f}(c_{1},c_{2},\dots,c_{n})$,
then for every $i\leq n$ it holds that $f(e_{i})\leq c_{i}\sqrt{i}f(b_{i})$.

###### Proof.

Let $i\leq n$ and note that $(b_{1},b_{2},\dots,b_{i-1})$ spans an
$i$-dimensional subspace of $V$, whereas $(e_{1},e_{2},\dots,e_{i})$ spans an
$i$-dimensional subspace of $V$. Hence there is a non-zero vector
$b^{\prime}\in span(e_{1},\dots,e_{i})$ that is orthogonal to all the vectors
$b_{1},b_{2},\dots,b_{i-1}$. Indeed, it is straightforward that the system:

$\sum_{j=1}^{i}\alpha_{j}\left<{e_{j},b_{k}}\right>=0\text{ for }k\leq i-1$

is overdetermined. Hence it admits a non-zero solution
$\alpha=(\alpha_{1},\dots,\alpha_{i})$ and since $e_{1},\dots,e_{i}$ are
independent, $b^{\prime}=\sum_{j=1}^{i}\alpha_{j}e_{j}$ is non-zero. Next,
without loss of generality, we may and we do assume that $\|b^{\prime}\|=1$.
Thus $b^{\prime}\in\mathbb{S}_{1}$ and $b^{\prime}$ is orthogonal to all the
vectors $b_{1},\dots,b_{i-1}$. By the definition of $b_{i}$, it follows that:

$f(b_{i})\leq
f(b^{\prime})=f\left(\sum_{j=1}^{i}\alpha_{j}e_{j}\right)\leq\sum_{j=1}^{i}|\alpha_{j}|f(e_{j}),$

where the last inequality follows by the triangle inequality. Finally, by the
arrangement of the vectors $e_{1},\dots,e_{i}$ we have $f(e_{j})\leq f(e_{i})$
for every $j\leq i$ and by the Cauchy-Schwartz inequality we have
$\sum_{j=1}^{i}|\alpha_{j}|\leq\sqrt{i}\sqrt{\sum_{j=1}^{i}|\alpha_{j}|^{2}}=\sqrt{i}$.
Summing up we obtain:

$f(b_{i})\leq\sum_{j=1}^{i}|\alpha_{j}|f(e_{j})\leq\sum_{j=1}^{i}|\alpha_{j}|f(e_{i})\leq\sqrt{i}f(e_{i}).$

For the second part of the statement, we proceed similarly. Let $i\leq n$.
Then $(b_{1},\dots,b_{i})$ span a linear space of dimensionality $i$ whereas
$(e_{1},\dots,e_{i-1})$ span a linear space of dimensionality $i-1$. Then, as
above, there is a non-zero vector $v\in span(b_{1},\dots,b_{i})$ that is
orthogonal to all the vectors $e_{1},\dots,e_{i-1}$. Without loss of
generality we may and we do assume that $v$ is a unit vector. Since $v$ is
orthogonal to $e_{1},\dots,e_{i-1}$, it belongs to the linear space spanned by
$(e_{i},\dots,e_{n})$. Hence $v$ can be written as
$v=\sum_{j=i}^{n}\alpha_{j}e_{j}$. By the $HP_{f}(c_{1},\dots,c_{n})$ of the
basis $(e_{1},\dots,e_{n})$, we conclude that:

$c_{i}f(v)=c_{i}f\left(\sum_{j=i}^{n}\alpha_{j}e_{j}\right)\geq\sum_{j=i}^{n}|\alpha_{j}|f(e_{j})\geq\sum_{j=i}^{n}|\alpha_{j}|f(e_{i})\geq
f(e_{i}),$

where the last but one inequality follows by the ordering of the vectors
$(e_{1},\dots,e_{n})$ and the last inequality follows by the fact that
$\sum_{j=i}^{n}|\alpha_{j}|^{2}=1$, as $v$ is a unit vector.

On the other hand, $v\in span(b_{1},\dots,b_{i})$ and hence
$v=\sum_{j=1}^{i}\beta_{j}b_{j}$. Since $\|v\|=1$, we have that
$\sum_{j=1}^{i}|\beta_{j}|^{2}=1$. Therefore, applying the triangle
inequality, we obtain:

$f(v)=f\left(\sum_{j=1}^{i}\beta_{j}b_{j}\right)\leq\sum_{j=1}^{i}|\beta_{j}|f(b_{j})\leq\sum_{j=1}^{i}|\beta_{j}|f(b_{i})\leq\sqrt{i}f(b_{i}),$

where the last but one inequality follows by the order of
$(b_{1},\dots,b_{n})$ and the last one is a trivial application of the Cauchy-
Schwartz inequality.

Summing up we get:

$f(e_{i})\leq c_{i}f(v)\leq c_{i}\sqrt{i}f(b_{i})$

as claimed. ∎

######  Corollary 10.

Let $f:V\rightarrow\mathbb{R}^{+}$ be a norm and $(b_{1},b_{2},\dots,b_{n})$
and $(e_{1},e_{2},\dots,e_{n})$ be orthonormal bases such that:

$\displaystyle f(b_{1})\leq f(b_{2})\leq\dots\leq f(b_{n})$ and $\displaystyle
f(e_{1})\leq f(e_{2})\leq\dots\leq f(e_{n}).$

  1. (1)

If $(b_{1},\dots,b_{n})$ and $(e_{1},\dots,e_{n})$ are $f$-minimal, then

$\frac{1}{\sqrt{i}}\leq\frac{f(b_{i})}{f(e_{i})}\leq\sqrt{i}.$

  2. (2)

If $(b_{1},\dots,b_{n})$ is $f$-minimal and $f$-maximal basis
$(e_{1},\dots,e_{n})$, then
$\frac{1}{\sqrt{i}(2^{n-i+1}-1)}\leq\frac{f(b_{i})}{f(e_{i})}\leq\sqrt{i}$.

  3. (3)

If $(b_{1},\dots,b_{n})$ and $(e_{1},\dots,e_{n})$ are $f$-maximal, then

$\frac{1}{\sqrt{i}(2^{n-i+1}-1)}\leq\frac{f(b_{i})}{f(e_{i})}\leq\sqrt{i}(2^{n-i+1}-1).$

Under certain additional assumptions, Lemma 9 can be inverted as follows:

######  Proposition 11.

Assume that $f:V\rightarrow\mathbb{R}^{+}$ is a norm and $(b_{1},\dots,b_{n})$
and $(e_{1},\dots,e_{n})$ and $c\geq 1$ are orthonormal bases for $V$ such
that:

$\displaystyle f(b_{1})\leq f(b_{2})\leq\dots\leq f(b_{n})$ $\displaystyle
f(e_{1})\leq f(e_{2})\leq\dots\leq f(e_{n})$ $\displaystyle\forall
i(f(e_{i})/c\leq f(b_{i})\leq cf(e_{i})).$

If $(b_{1},\dots,b_{n})$ satisfies $H_{f}(c_{1})$ and additionally there is
$\alpha\geq 1$ such that:

$\forall i\neq j\exists\alpha_{i,j}(|\alpha_{i,j}|<\alpha\text{ and
}\left<{e_{i}-b_{i},e_{j}-\alpha_{i,j}b_{j}}\right>=0),$

then $(e_{1},\dots,e_{n})$ satisfies $H_{f}(\alpha c^{2}c_{1})$.

###### Proof.

Since $(b_{1},\dots,b_{n})$ satisfies $H_{f}(c_{1})$, it follows that:

$c_{1}f(e_{i})\geq\sum_{j=1}^{n}|\left<{e_{i},b_{j}}\right>|f(b_{j}).$

Hence:

$\displaystyle f(b_{i})$ $\displaystyle\geq$ $\displaystyle f(e_{i})/c$
$\displaystyle\geq$ $\displaystyle c_{1}f(e_{i})/(cc_{1})$ $\displaystyle\geq$
$\displaystyle\sum_{j=1}^{n}|\left<{e_{i},b_{j}}\right>|f(b_{j})/c$
$\displaystyle\geq$
$\displaystyle\frac{1}{c^{2}}\sum_{j=1}^{n}|\left<{e_{i},b_{j}}\right>|f(e_{j}).$

Note that the condition $\left<{e_{i}-b_{i},e_{j}-\alpha_{i,j}b_{j}}\right>=0$
can be rewritten as:

$\left<{e_{i},e_{j}}\right>+\overline{\alpha_{i,j}}\left<{b_{i},b_{j}}\right>-\left<{b_{i},e_{j}}\right>-\overline{\alpha_{i,j}}\left<{e_{i},b_{j}}\right>=0.$

For $i\neq j$ it holds that
$\left<{b_{i},b_{j}}\right>=\left<{e_{i},e_{j}}\right>=0$ and therefore for
$i\neq j$ we have:

$|\left<{b_{i},e_{j}}\right>|=|\alpha_{i,j}||\left<{e_{i},b_{j}}\right>|\leq\alpha|\left<{e_{i},b_{j}}\right>|.$

Hence the above inequality implies that:

$f(b_{i})\geq\frac{1}{c^{2}}\sum_{j=1}^{n}|\left<{e_{i},b_{j}}\right>|f(e_{j})\geq\frac{1}{\alpha
c^{2}}\sum_{j=1}^{n}|\left<{b_{i},e_{j}}\right>|f(e_{j}).$

Therefore:

$\alpha c^{2}f(b_{i})\geq\sum_{j=1}^{n}|\left<{b_{i},e_{j}}\right>|f(e_{j}).$

Finally, for arbitrary $v$ the above inequality and the validity of
$H_{f}(c_{1})$ for the basis $(b_{1},\dots,b_{n})$ imply:

$\displaystyle\alpha c^{2}c_{1}f(v)$ $\displaystyle\geq$ $\displaystyle\alpha
c^{2}\sum_{i=1}^{n}|\left<{v,b_{i}}\right>|f(b_{i})$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}|\left<{v,b_{i}}\right>||\left<{b_{i},e_{j}}\right>|f(e_{j})$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n}f(e_{j})\sum_{i=1}^{n}|\left<{v,b_{i}}\right>\left<{b_{i},e_{j}}\right>|$
$\displaystyle\geq$
$\displaystyle\sum_{j=1}^{n}f(e_{j})\left|\sum_{i=1}^{n}\left<{v,b_{i}}\right>\left<{b_{i},e_{j}}\right>\right|$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n}|\left<{v,e_{j}}\right>|f(e_{j}).$

This proves that $(e_{1},\dots,e_{n})$ satisfies $H_{f}(\alpha c^{2}c_{1})$.

∎

##  6\. Open Problems

The definitions of $f$-minimal and $f$-maximal bases of a norm suggest a
simple greedy strategy to find an orthonormal basis $(e_{1},\dots,e_{n})$
which satisfies the inequality:

$f(\sum_{i=1}^{n}\alpha_{i}e_{i})\geq\frac{1}{2^{n}-1}\sum_{i=1}^{n}|\alpha_{i}|f(e_{i}).$

Of course, the feasibility of this approach depends on the possibility to
efficiently solve the optimisation problem:

$\max_{v\in\mathbb{S}_{1}}f(v)\text{ or }\min_{v\in\mathbb{S}_{1}}f(v).$

Yet, since every (semi)norm $f$ is convex and $\mathbb{S}_{1}$ is compact,
especially the second problem is well studied and efficient methods for its
solution stay at hand.

However, the problem with the greedy approach is that the constant $2^{n}-1$
grows exponentially with $n$ and it may be inconvenient to prove precise
bounds in general. As we have proven in Lemma 6 and Lemma 7, the constant
$2^{n}-1$ cannot be improved under the suggested greedy strategy. Thus, the
natural question that arises is how this constant can be improved while
preserving the clear structure of the bases that it implies. In this respect,
we consider the following theoretical problems.

First, for a natural number $n\geq 1$, and a linear vector space $V$ with
inner product, where $V=\mathbb{C}^{n}$ or $V=\mathbb{R}^{n}$. We define
$c_{n}^{\perp}:=c_{n}^{\perp}(V)$ to be the least real number such that for
every norm $f:V\rightarrow\mathbb{R}^{+}$ there is an orthonormal basis
$(b_{1},\dots,b_{n})$ such that:

$f(\sum_{i=1}^{n}\alpha_{i}b_{i})\geq\frac{1}{c_{n}^{\perp}}\sum_{i=1}^{n}|\alpha_{i}|f(b_{i})\text{
for all }\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}.$

It is known that for $V=\mathbb{R}^{2}$, $c_{2}^{\perp}=2$, [6]. The
construction in [6] relies upon defining appropriate areas and the continuity
principle to show existence. Is there a more explicit way to define such a
basis? To the best knowledge of the authors, the techniques from $n=2$ do not
extend to higher dimensions.

Secondly, for a natural number $n\geq 1$, and a linear vector space $V$ with
inner product, where $V=\mathbb{C}^{n}$ or $V=\mathbb{R}^{n}$. We define
$c_{n}^{\angle}=c_{n}^{\angle}(V)$ to be the least real number such that for
every norm $f:V\rightarrow\mathbb{R}^{+}$ there is an basis
$(b_{1},\dots,b_{n})$ of unit vectors such that:

$f(\sum_{i=1}^{n}\alpha_{i}b_{i})\geq\frac{1}{c_{n}^{\angle}}\sum_{i=1}^{n}|\alpha_{i}|f(b_{i})\text{
for all }\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}.$

It is known that for $V=\mathbb{R}^{2}$, $c_{2}^{\angle}=\frac{3}{2}$,
[1].This question is tightly related with John’s Theorem [5] which relies on
volumes’ optimisation.

Both questions can be uniformly stated as follows. Let $n\geq 1$, and
$V=\mathbb{C}^{n}$ or $V=\mathbb{R}^{n}$ and $\alpha\in[0,1]$. Define
$c_{n}^{\alpha}:=c_{n}^{\alpha}(V)$ to be the least real number such that for
every norm $f:V\rightarrow\mathbb{R}^{+}$ there is a basis
$(b_{1},\dots,b_{n})$ of unit vectors such that:

$\displaystyle f\left(\sum_{i=1}^{n}\alpha_{i}b_{i}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{c_{n}^{\alpha}}\sum_{i=1}^{n}|\alpha_{i}|f(b_{i})\text{
for all }\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}$ $\displaystyle\text{subject
to}:|\left<{b_{i},b_{j}}\right>|$ $\displaystyle\leq$
$\displaystyle\alpha\text{ for all }i\neq j.$

In this framework, $c_{n}^{\perp}(V)=c_{n}^{0}(V)$ and
$c_{n}^{\angle}(V)=c_{n}^{1}(V)$. We consider that the freedom to vary
$\alpha$ may be useful in applications where this kind of inequalities are to
be combined with other classical inequalities where the scalar products of the
basis’ vectors has to be controlled.

## References

  * [1] Edgar Asplund.  Comparison between Plane Symmetric Convex Bodies and Parallelograms.  Marh. Scand., 8:171–180, 1960.
  * [2] Philip Charpentier and Yves Dupain.  Extremal Bases, Geometrically Separated Domains and Applications.  Algebra and Analysis, 26(1):196–269, 2014.
  * [3] Tosten Hefer.  Hölder and $l^{p}$ Estimates for $\overline{\partial}$ on Convex Domains of Finite Type Depending on Catlin’s Multiptype.  Mathematische Zeitschrift, 242:367–398, 2002.
  * [4] Tosten Hefer.  Extremal Bases and Hölder Estimates for $\overline{\partial}$ on Convex Domains of Finite Type.  Michigan Math. J., 52:573–602, 2004.
  * [5] Fritz John.  Extremum Problems with Inequalities as Subsidary Conditions.  In In Studies and Essays presented to R. Courant on his 60th birthday,, pages 187–204. Interscience Publishers Inc., 1948.
  * [6] Marek Lassak.  Approximation of Convex Bodies By Axially Symmetric Bodies.  Proceedings of the American Mathematical Society, 130(10):3075–3084, 2002.
  * [7] Jeffery D. McNeal.  Convex Domains of Finite Types.  Journal of Functional Analysis, 108:361–373, 1992.
  * [8] Jeffery D. McNeal.  Estimates on the Bergman Kernels of Convex Domains.  Advances in Mathematics, 109:108–139, 1994.
  * [9] Nikolai Nikolov and Peter Pflug.  Estimates for the Bergman Kernel and Metric of Convex Domains in $\mathbb{C}^{n}$.  Annales Polonici Mathematici, 81(1):73–78, 2003.
  * [10] Nikolai Nikolov, Peter Pflug, and Pascal J. Thomas.  On Different Extremal Bases for $\mathbb{C}$-convex Domains.  Proceedings of the American Mathematical Society, 141(9):3223–3230, 2013.
  * [11] Nikolai Nikolov, Peter Pflug, and Wlodzimierz Zwonek.  Estimates for Invariant Metrics on $\mathbb{C}$-convex Domains.  Transactions of the American Mathematical Society, 363(12):6245–6256, 2011.
  * [12] Hongyu Wang.  Estimates of the Kobayashi Metric and Gromov Hyperbolicity on Convex Domains of Finite Type, 2022.


# A note on Woodin’s HOD dichotomy

Gabriel Goldberg
Evans Hall
University Drive
Berkeley, CA 94720

##  1 Introduction

The purpose of this note is to prove a version of Woodin’s HOD dichotomy [4]
from a strongly compact cardinal. A cardinal $\kappa$ is strongly compact if
every $\kappa$-complete filter extends to a $\kappa$-complete ultrafilter. The
class of hereditarily ordinal definable sets, denoted HOD, is the minimum
class $M$ that contains all the ordinals and is definably closed: if
$S\subseteq M$ is definable (in the universe of sets $V$) by a set theoretic
formula with parameters in $M$, then $S\in M$. HOD is a proper class
transitive model of ZFC.

######  Theorem 1.1.

Suppose $\kappa$ is strongly compact. Then one of the following holds:

  1. (1)

For every singular strong limit cardinal $\lambda\geq\kappa$, $\lambda$ is
singular in HOD and $\lambda^{+\textnormal{HOD}}=\lambda^{+}$.

  2. (2)

All sufficiently large regular cardinals are measurable in HOD.

If 1 holds, 2 cannot (since there are arbitrarily large successor cardinals
that are not inaccessible in HOD), so 1.1 is truly a dichotomy.

We will actually prove a stronger dichotomy. An inner model $M$ is said to
have the $\lambda$-cover property if every set of ordinals of cardinality less
than $\lambda$ is covered by (that is, included in) a set of ordinals in $M$
of cardinality less than $\lambda$.

######  Theorem 1.2.

Suppose $\kappa$ is strongly compact. Then one of the following holds:

  1. (1)

For every strong limit cardinal $\lambda\geq\kappa$, HOD has the
$\lambda$-cover property.

  2. (2)

All sufficiently large regular cardinals are $\omega$-strongly measurable in
HOD.

The definition of $\omega$-strong measurability is deferred until the
beginning of the next section, but let us note here that any cardinal that is
$\omega$-strongly measurable in HOD is indeed measurable in HOD. Note that 1.2
1 strengthens 1.1 1, while 1.2 2 strengthens 1.1 2.

Assuming instead that $\kappa$ is HOD-supercompact, Woodin [4] proved an even
stronger dichotomy theorem, for example establishing that if (either)
condition 1 above holds, then $\kappa$ is supercompact in HOD. On the other
hand, Cheng-Friedman-Hamkins [1] produce a model of ZFC with a supercompact
cardinal $\kappa$ in which 1 holds, yet $\kappa$ is not weakly compact in HOD,
which shows that Woodin’s theorem cannot be proved from the hypotheses we
assume here.

##  2 The proof

Suppose $\delta$ is a regular cardinal and $S\subseteq\delta$ is a stationary
set. We say an inner model $M$ splits $S$ if $S\in M$ and for all $\gamma$
such that $(2^{\gamma})^{M}<\delta$, there is a partition of $S$ into
$\gamma$-many stationary sets. A cardinal is $\omega$-strongly measurable in
HOD if HOD does not split the set of ordinals less than $\delta$ with
countable cofinality, which is denoted by $S^{\delta}_{\omega}$.

######  Theorem 2.1 (Woodin, [4, Lemma 3.37]).

If $S$ is an ordinal definable stationary subset of a regular cardinal
$\delta$ and HOD does not split $S$, then $(\mathcal{C}_{\delta}\restriction
S)\cap\textnormal{HOD}$ is atomic in HOD. In particular, if $\delta$ is
$\omega$-strongly measurable in HOD, then $\delta$ is measurable in HOD and
$\delta$ contains an $\omega$-club of cardinals inaccessible in HOD.

The last sentence is supposed to highlight that the existence of
$\omega$-strongly measurable cardinals entails a massive failure of the cover
property even for countable sets. Actually there is an $\omega_{1}$-club of
cardinals measurable in HOD below any cardinal that is $\omega_{1}$-strongly
measurable in HOD in the natural sense.

######  Proposition 2.2.

Suppose $\kappa$ is strongly compact, $\delta\geq\kappa$ is regular, and HOD
splits $S^{\delta}_{\omega}$. Then for any $\gamma$ such that
$(2^{\gamma})^{\textnormal{HOD}}<\delta$, there is a $\kappa$-complete fine
ultrafilter $\mathcal{U}$ on $P_{\kappa}(\gamma)$ such that $\mathcal{U}$
concentrates on $P_{\kappa}(\gamma)\cap\textnormal{HOD}$.

###### Proof.

Let $j:V\to M$ be an elementary embedding from the universe into an inner
model such that $\textnormal{crit}(j)=\kappa$ and $j[\delta]$ is contained in
some set $S\in M$ with $|S|^{M}<j(\kappa)$. In particular, the ordinal
$\delta_{*}=\sup j[\delta]$ has cofinality less than $j(\kappa)$ in $M$. Let
$C\subseteq\delta_{*}$ be a closed unbounded set of ordertype
$\textnormal{cf}^{M}(\delta_{*})$.

Fix a cardinal $\gamma$ such that $(2^{\gamma})^{\textnormal{HOD}}<\delta$ and
let $\langle S_{\alpha}\rangle_{\alpha<\gamma}$ witness that HOD splits
$S^{\delta}_{\omega}$. Then let

$\sigma=\\{\xi<j(\gamma):T_{\xi}\cap\delta_{*}\text{ is stationary in }M\\}$

where $\vec{T}=j(\vec{S})$. Thus $\sigma\in\textnormal{HOD}^{M}$. Notice that
$j[\gamma]\subseteq\sigma$: $j[S_{\xi}]\subseteq T_{j(\xi)}$, so in fact
$T_{j(\xi)}\cap\delta_{*}$ is truly stationary (not just in $M$). For all
$\xi\in\sigma$, $T_{\xi}\cap C\neq\emptyset$, so let $f(\xi)=\min(T_{\xi}\cap
C)$. Then $f:\sigma\to C$ is an injection. So
$|\sigma|=\textnormal{cf}^{M}(\delta_{*})$. In particular, $\sigma\in
j(P_{\kappa}(\gamma))$.

Finally let $\mathcal{U}$ be the ultrafilter on $P_{\kappa}(\gamma)$ derived
from $j$ using $\sigma$. That is, let $\mathcal{U}=\\{A\subseteq
P_{\kappa}(\gamma):\sigma\in j(A)\\}$. Since $\sigma\in\textnormal{HOD}^{M}$,
$\sigma\in j(P_{\kappa}(\gamma)\cap\textnormal{HOD})$, and hence
$\textnormal{HOD}\cap P_{\kappa}(\gamma)\in\mathcal{U}$. Since
$j[\gamma]\subseteq\sigma$, $\mathcal{U}$ is fine. Since
$\textnormal{crit}(j)=\kappa$, $\mathcal{U}$ is $\kappa$-complete. ∎

The main observation involved in the proof above is that the stationary
splitting argument from [4] (which Woodin calls “Solovay’s Lemma” although it
is a bit different from the related lemma in [2]) can be adapted to strongly
compact cardinals. Usuba [3] made the same observation independently and
earlier.

######  Lemma 2.3.

Suppose $\kappa$ is strongly compact. Then one of the following holds:

  1. (1)

HOD has the $\kappa$-cover property.

  2. (2)

All sufficiently large regular cardinals are $\omega$-strongly measurable in
in HOD.

###### Proof.

Assume that there are arbitrarily large regular cardinals $\delta$ that are
not $\omega$-strongly measurable in HOD, or in other words, HOD splits
$S^{\delta}_{\omega}$. Applying 2.2 to sufficiently large such $\delta$, for
all $\gamma\geq\kappa$, there is a $\kappa$-complete fine ultrafilter
$\mathcal{U}$ on $P_{\kappa}(\gamma)$ such that
$P_{\kappa}(\gamma)\cap\textnormal{HOD}\in\mathcal{U}$. For each $\sigma\in
P_{\kappa}(\gamma)$, $\\{\tau\in
P_{\kappa}(\gamma):\sigma\subseteq\tau\\}\in\mathcal{U}$. Since $\mathcal{U}$
is a filter, it follows that $\\{\tau\in
P_{\kappa}(\gamma)\cap\textnormal{HOD}:\sigma\subseteq\tau\\}\in\mathcal{U}$,
and in particular this set is nonempty. This yields $\tau\in
P_{\kappa}(\gamma)\cap\textnormal{HOD}$ covering $\sigma$, as desired. ∎

We now extend the cover property of HOD to all strong limit cardinals greater
than or equal to the first strongly compact cardinal.

###### Proof of 1.2.

Suppose 2 fails, so by 2.3, HOD has the $\kappa$-cover property. Given this,
it suffices to show that for all $\delta\geq\kappa$, for some
$\delta^{\prime}<\beth_{\omega}(\delta)$, every set of ordinals of cardinality
at most $\delta$ is covered by a set of ordinals in HOD of cardinality at most
$\delta^{\prime}$.

Let $\mathcal{U}$ be a fine $\kappa$-complete ultrafilter on
$P_{\kappa}(\delta)$. Fix $A\subseteq\kappa$ such that
$V_{\kappa}\subseteq\textnormal{HOD}_{A}$. We will show that for every set $S$
of ordinals of cardinality at most $\delta$, there is a set $T$ of cardinality
at most $2^{\delta}$ such that $T\in\textnormal{HOD}_{A,\mathcal{U}}$ and
$S\subseteq T$. By Vopenka’s theorem, $\textnormal{HOD}_{A,\mathcal{U}}$ is a
forcing extension of HOD by a forcing in HOD of cardinality less than
$\beth_{\omega}(\delta)$, so the theorem follows.

Note that $\textnormal{HOD}_{A,\mathcal{U}}$ is closed under
${<}\kappa$-sequences since $\textnormal{HOD}_{A,\mathcal{U}}$ has the
$\kappa$-cover property and
$V_{\kappa}\subseteq\textnormal{HOD}_{A,\mathcal{U}}$. As a consequence,
$M_{\mathcal{U}}$ satisfies that
$j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})$ is closed under
${<}j_{\mathcal{U}}(\kappa)$-sequences. Also
$j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})\subseteq\textnormal{HOD}_{A,\mathcal{U}}$:
there is a wellorder of $j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})$
definable from $A$ and $\mathcal{U}$.

Finally, suppose $S$ is a set of ordinals of cardinality at most $\delta$.
Then since $\mathcal{U}$ is fine, there is some $T$ in $M_{\mathcal{U}}$ such
that $S\subseteq T$ and $|T|^{M_{\mathcal{U}}}<j_{\mathcal{U}}(\delta)$.
Therefore $T\in
j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})\subseteq\textnormal{HOD}_{A,\mathcal{U}}$.
Moreover $|T|\leq|j_{\mathcal{U}}(\delta)|\leq 2^{\delta}$. This completes the
proof. ∎

It may be unclear where we used that $\kappa\neq\omega$ in the proof above. In
fact, we used the countable completeness of $\mathcal{U}$ to establish that
there is a wellorder of $j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})$
definable from $A$ and $\mathcal{U}$. (If $\mathcal{U}$ is countably
incomplete, the canonical wellorder of
$j_{\mathcal{U}}(\textnormal{HOD}_{A,\mathcal{U}})$ as computed in
$M_{\mathcal{U}}$ is not a wellorder at all.)

Using these theorems, we prove the dichotomy involving successors of
singulars.

###### Proof of 1.1.

By 2.3 (and 2.1), we can assume that HOD has the $\kappa$-cover property. Fix
a singular strong limit cardinal $\lambda>\kappa$. 1.2 easily implies that
$\lambda$ is singular in HOD. Let $\gamma=\lambda^{+\textnormal{HOD}}$. Since
$\gamma$ is regular in HOD, 1.2 implies $\textnormal{cf}(\gamma)\geq\lambda$.
Since $\lambda$ is singular, $\textnormal{cf}(\gamma)>\lambda$, and so
$\gamma=\lambda^{+}$. ∎

## References

  * [1] Yong Cheng, Sy-David Friedman, and Joel David Hamkins.  Large cardinals need not be large in HOD.  Annals of Pure and Applied Logic, 166(11):1186 – 1198, 2015.
  * [2] Robert M. Solovay, William N. Reinhardt, and Akihiro Kanamori.  Strong axioms of infinity and elementary embeddings.  Ann. Math. Logic, 13(1):73–116, 1978.
  * [3] Toshimichi Usuba.  A note on $\delta$-strongly compact cardinals.  Topology and its Applications, page 107538, 2020.
  * [4] W. Hugh Woodin.  In search of Ultimate-$L$: the 19th Midrasha Mathematicae Lectures.  Bull. Symb. Log., 23(1):1–109, 2017.