imported>Nerdican: /* Definitions */ Replaced erroneous inequality with correct equality

2025-04-18T17:21:29Z

Definitions: Replaced erroneous inequality with correct equality

New page

{{Short description|Type of function in linear algebra}}
In [[linear algebra]], a '''sublinear''' function (or [[Functional (mathematics)|functional]] as is more often used in [[functional analysis]]), also called a '''quasi-seminorm''' or a '''Banach functional''', on a [[vector space]] <math>X</math> is a [[Real number|real]]-valued [[Function (mathematics)|function]] with only some of the properties of a [[seminorm]]. Unlike seminorms, a sublinear function does not have to be [[nonnegative]]-valued and also does not have to be [[absolutely homogeneous]]. Seminorms are themselves abstractions of the more well known notion of [[Norm (mathematics)|norms]], where a seminorm has all the defining properties of a norm {{em|except}} that it is not required to map non-zero vectors to non-zero values.

In [[functional analysis]] the name '''Banach functional''' is sometimes used, reflecting that they are most commonly used when applying a general formulation of the [[Hahn–Banach theorem]].
The notion of a sublinear function was introduced by [[Stefan Banach]] when he proved his version of the [[Hahn-Banach theorem]].{{sfn|Narici|Beckenstein|2011|pp=177-220}}

There is also a different notion in [[computer science]], described below, that also goes by the name "sublinear function."

==Definitions==

Let <math>X</math> be a [[vector space]] over a field <math>\mathbb{K},</math> where <math>\mathbb{K}</math> is either the [[real number]]s <math>\Reals</math> or [[complex number]]s <math>\C.</math>
A real-valued function <math>p : X \to \mathbb{R}</math> on <math>X</math> is called a ''{{em|{{visible anchor|sublinear function}}}}'' (or a ''{{em|{{visible anchor|sublinear functional|text=sublinear [[functional (mathematics)|functional]]}}}}'' if <math>\mathbb{K} = \Reals</math>), and also sometimes called a ''{{em|{{visible anchor|quasi-seminorm}}}}'' or a ''{{em|{{visible anchor|Banach functional}}}}'', if it has these two properties:{{sfn|Narici|Beckenstein|2011|pp=177-220}}
<ol>
<li>''[[Positive homogeneity]]'''/'''[[Nonnegative homogeneity]]'':{{sfn|Schechter|1996|pp=313-315}} <math>p(r x) = r p(x)</math> for all real <math>r \geq 0</math> and all <math>x \in X.</math>
* This condition holds if and only if <math>p(r x) = r p(x)</math> for all positive real <math>r > 0</math> and all <math>x \in X.</math></li>
<li>''[[Subadditivity]]'''/'''[[Triangle inequality]]'':{{sfn|Schechter|1996|pp=313-315}} <math>p(x + y) \leq p(x) + p(y)</math> for all <math>x, y \in X.</math>
* This subadditivity condition requires <math>p</math> to be real-valued.</li>
</ol>

A function <math>p : X \to \Reals</math> is called {{em|{{visible anchor|positive}}}}{{sfn|Narici|Beckenstein|2011|pp=120-121}} or {{em|{{visible anchor|nonnegative}}}} if <math>p(x) \geq 0</math> for all <math>x \in X,</math> although some authors{{sfn|Kubrusly|2011|p=200}} define {{em|{{visible anchor|positive}}}} to instead mean that <math>p(x) \neq 0</math> whenever <math>x \neq 0;</math> these definitions are not equivalent.
It is a {{em|{{visible anchor|symmetric function}}}} if <math>p(-x) = p(x)</math> for all <math>x \in X.</math>
Every subadditive symmetric function is necessarily nonnegative.<ref group=proof name=SubadditiveSymmetricIsNonnegative />
A sublinear function on a real vector space is [[#symmetric function|symmetric]] if and only if it is a [[seminorm]].
A sublinear function on a real or complex vector space is a seminorm if and only if it is a [[balanced function]] or equivalently, if and only if <math>p(u x) \leq p(x)</math> for every [[unit length]] scalar <math>u</math> (satisfying <math>|u| = 1</math>) and every <math>x \in X.</math>

The set of all sublinear functions on <math>X,</math> denoted by <math>X^{\#},</math> can be [[Partial order|partially ordered]] by declaring <math>p \leq q</math> if and only if <math>p(x) \leq q(x)</math> for all <math>x \in X.</math>
A sublinear function is called ''{{em|minimal}}'' if it is a [[minimal element]] of <math>X^{\#}</math> under this order.
A sublinear function is minimal if and only if it is a real [[linear functional]].{{sfn|Narici|Beckenstein|2011|pp=177-220}}

==Examples and sufficient conditions==

Every [[Norm (mathematics)|norm]], [[seminorm]], and real linear functional is a sublinear function.
The [[identity function]] <math>\Reals \to \Reals</math> on <math>X := \Reals</math> is an example of a sublinear function (in fact, it is even a linear functional) that is neither positive nor a seminorm; the same is true of this map's negation <math>x \mapsto -x.</math>{{sfn|Narici|Beckenstein|2011|pp=177-221}}
More generally, for any real <math>a \leq b,</math> the map
<math display=block>\begin{alignat}{4}
S_{a,b} :\;&& \Reals &&\;\to \;& \Reals \\[0.3ex]
&& x &&\;\mapsto\;&
\begin{cases}
a x & \text{ if } x \leq 0 \\
b x & \text{ if } x \geq 0 \\
\end{cases} \\
\end{alignat}</math>
is a sublinear function on <math>X := \Reals</math> and moreover, every sublinear function <math>p : \Reals \to \Reals</math> is of this form; specifically, if <math>a := - p(-1)</math> and <math>b := p(1)</math> then <math>a \leq b</math> and <math>p = S_{a, b}.</math>

If <math>p</math> and <math>q</math> are sublinear functions on a real vector space <math>X</math> then so is the map <math>x \mapsto \max \{p(x), q(x)\}.</math> More generally, if <math>\mathcal{P}</math> is any non-empty collection of sublinear functionals on a real vector space <math>X</math> and if for all <math>x \in X,</math> <math>q(x) := \sup \{p(x) : p \in \mathcal{P}\},</math> then <math>q</math> is a sublinear functional on <math>X.</math>{{sfn|Narici|Beckenstein|2011|pp=177-221}}

A function <math>p : X \to \Reals</math> which is [[Subadditivity|subadditive]], [[Convex function|convex]], and satisfies <math>p(0) \leq 0</math> is also positively homogeneous (the latter condition <math>p(0) \leq 0</math> is necessary as the example of <math>p(x):=\sqrt{x^2+1}</math> on <math>X:=\mathbb R</math> shows). If <math>p</math> is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming <math>p(0) \leq 0</math>, any two properties among subadditivity, convexity, and positive homogeneity implies the third.

==Properties==

Every sublinear function is a [[convex function]]: For <math>0 \leq t \leq 1,</math>
<math display=block>\begin{alignat}{3}
p(t x + (1 - t) y)
&\leq p(t x) + p((1 - t) y) && \quad\text{ subadditivity} \\
&= t p(x) + (1 - t) p(y) && \quad\text{ nonnegative homogeneity} \\
\end{alignat}</math>

If <math>p : X \to \Reals</math> is a sublinear function on a vector space <math>X</math> then<ref group=proof name=NullAtZeroAndSumUpperBound />{{sfn|Narici|Beckenstein|2011|pp=120-121}}
<math display=block>p(0) ~=~ 0 ~\leq~ p(x) + p(-x),</math>
for every <math>x \in X,</math> which implies that at least one of <math>p(x)</math> and <math>p(-x)</math> must be nonnegative; that is, for every <math>x \in X,</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}
<math display=block>0 ~\leq~ \max \{p(x), p(-x)\}.</math>
Moreover, when <math>p : X \to \Reals</math> is a sublinear function on a real vector space then the map <math>q : X \to \Reals</math> defined by <math>q(x) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(-x)\}</math> is a seminorm.{{sfn|Narici|Beckenstein|2011|pp=120-121}}

Subadditivity of <math>p : X \to \Reals</math> guarantees that for all vectors <math>x, y \in X,</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}<ref group=proof name=ReverseTriangle />
<math display=block>p(x) - p(y) ~\leq~ p(x - y),</math>
<math display=block>- p(x) ~\leq~ p(-x),</math>
so if <math>p</math> is also [[#symmetric function|symmetric]] then the [[reverse triangle inequality]] will hold for all vectors <math> x, y \in X,</math>
<math display=block>|p(x) - p(y)| ~\leq~ p(x - y).</math>

Defining <math>\ker p ~\stackrel{\scriptscriptstyle\text{def}}{=}~ p^{-1}(0),</math> then subadditivity also guarantees that for all <math>x \in X,</math> the value of <math>p</math> on the set <math>x + (\ker p \cap -\ker p) = \{x + k : p(k) = 0 = p(-k)\}</math> is constant and equal to <math>p(x).</math><ref group=proof name=ConstantOnEquivClasses />
In particular, if <math>\ker p = p^{-1}(0)</math> is a vector subspace of <math>X</math> then <math>- \ker p = \ker p</math> and the assignment <math>x + \ker p \mapsto p(x),</math> which will be denoted by <math>\hat{p},</math> is a well-defined real-valued sublinear function on the [[Quotient space (linear algebra)|quotient space]] <math>X \,/\, \ker p</math> that satisfies <math>\hat{p} ^{-1}(0) = \ker p.</math> If <math>p</math> is a seminorm then <math>\hat{p}</math> is just the usual canonical norm on the quotient space <math>X \,/\, \ker p.</math>

{{Math theorem
| name = {{visible anchor|Pryce's sublinearity lemma}}{{sfn|Schechter|1996|pp=313-315}}
| math_statement = Suppose <math>p : X \to \Reals</math> is a sublinear functional on a vector space <math>X</math> and that <math>K \subseteq X</math> is a non-empty convex subset.
If <math>x \in X</math> is a vector and <math>a, c > 0</math> are positive real numbers such that
<math display=block>p(x) + a c ~<~ \inf_{k \in K} p(x + a k)</math>
then for every positive real <math>b > 0</math> there exists some <math>\mathbf{z} \in K</math> such that
<math display=block>p(x + a \mathbf{z}) + b c ~<~ \inf_{k \in K} p(x + a \mathbf{z} + b k).</math>
}}

Adding <math>b c</math> to both sides of the hypothesis <math display=inline>p(x) + a c \,<\, \inf_{} p(x + a K)</math> (where <math>p(x + a K) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \{p(x + a k) : k \in K\}</math>) and combining that with the conclusion gives
<math display=block>p(x) + a c + b c ~<~ \inf_{} p(x + a K) + b c ~\leq~ p(x + a \mathbf{z}) + b c ~<~ \inf_{} p(x + a \mathbf{z} + b K)</math>
which yields many more inequalities, including, for instance,
<math display=block>p(x) + a c + b c ~<~ p(x + a \mathbf{z}) + b c ~<~ p(x + a \mathbf{z} + b \mathbf{z})</math>
in which an expression on one side of a strict inequality <math>\,<\,</math> can be obtained from the other by replacing the symbol <math>c</math> with <math>\mathbf{z}</math> (or vice versa) and moving the closing parenthesis to the right (or left) of an adjacent summand (all other symbols remain fixed and unchanged).

===Associated seminorm===

If <math>p : X \to \Reals</math> is a real-valued sublinear function on a real vector space <math>X</math> (or if <math>X</math> is complex, then when it is considered as a real vector space) then the map <math>q(x) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(-x)\}</math> defines a [[seminorm]] on the real vector space <math>X</math> called the '''seminorm associated with <math>p.</math>'''{{sfn|Narici|Beckenstein|2011|pp=120-121}}
A sublinear function <math>p</math> on a real or complex vector space is a [[#symmetric function|symmetric function]] if and only if <math>p = q</math> where <math>q(x) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(-x)\}</math> as before.

More generally, if <math>p : X \to \Reals</math> is a real-valued sublinear function on a (real or complex) vector space <math>X</math> then
<math display=block>q(x) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \sup_{|u|=1} p(u x) ~=~ \sup \{p(u x) : u \text{ is a unit scalar }\}</math>
will define a [[seminorm]] on <math>X</math> if this supremum is always a real number (that is, never equal to <math>\infty</math>).

===Relation to linear functionals===

If <math>p</math> is a sublinear function on a real vector space <math>X</math> then the following are equivalent:{{sfn|Narici|Beckenstein|2011|pp=177-220}}
<ol>
<li><math>p</math> is a [[linear functional]].</li>
<li>for every <math>x \in X,</math> <math>p(x) + p(-x) \leq 0.</math></li>
<li>for every <math>x \in X,</math> <math>p(x) + p(-x) = 0.</math></li>
<li><math>p</math> is a minimal sublinear function.</li>
</ol>

If <math>p</math> is a sublinear function on a real vector space <math>X</math> then there exists a linear functional <math>f</math> on <math>X</math> such that <math>f \leq p.</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}

If <math>X</math> is a real vector space, <math>f</math> is a linear functional on <math>X,</math> and <math>p</math> is a positive sublinear function on <math>X,</math> then <math>f \leq p</math> on <math>X</math> if and only if <math>f^{-1}(1) \cap \{x \in X : p(x) < 1\} = \varnothing.</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}

====Dominating a linear functional====

A real-valued function <math>f</math> defined on a subset of a real or complex vector space <math>X</math> is said to be {{em|dominated by}} a sublinear function <math>p</math> if <math>f(x) \leq p(x)</math> for every <math>x</math> that belongs to the domain of <math>f.</math>
If <math>f : X \to \Reals</math> is a real [[linear functional]] on <math>X</math> then{{sfn|Rudin|1991|pp=56-62}}{{sfn|Narici|Beckenstein|2011|pp=177-220}} <math>f</math> is dominated by <math>p</math> (that is, <math>f \leq p</math>) if and only if <math display=block>-p(-x) \leq f(x) \leq p(x) \quad \text{ for every } x \in X.</math>
Moreover, if <math>p</math> is a seminorm or some other {{em|symmetric map}} (which by definition means that <math>p(-x) = p(x)</math> holds for all <math>x</math>) then <math>f \leq p</math> if and only if <math>|f| \leq p.</math>

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=177-220}}|math_statement=
If <math>p : X \to \Reals</math> be a sublinear function on a real vector space <math>X</math> and if <math>z \in X</math> then there exists a linear functional <math>f</math> on <math>X</math> that is dominated by <math>p</math> (that is, <math>f \leq p</math>) and satisfies <math>f(z) = p(z).</math>
Moreover, if <math>X</math> is a [[topological vector space]] and <math>p</math> is continuous at the origin then <math>f</math> is continuous.
}}

===Continuity===

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=
Suppose <math>f : X \to \Reals</math> is a subadditive function (that is, <math>f(x + y) \leq f(x) + f(y)</math> for all <math>x, y \in X</math>).
Then <math>f</math> is continuous at the origin if and only if <math>f</math> is uniformly continuous on <math>X.</math>
If <math>f</math> satisfies <math>f(0) = 0</math> then <math>f</math> is continuous if and only if its absolute value <math>|f| : X \to [0, \infty)</math> is continuous.
If <math>f</math> is non-negative then <math>f</math> is continuous if and only if <math>\{x \in X : f(x) < 1\}</math> is open in <math>X.</math>
}}

Suppose <math>X</math> is a [[topological vector space]] (TVS) over the real or complex numbers and <math>p</math> is a sublinear function on <math>X.</math>
Then the following are equivalent:{{sfn|Narici|Beckenstein|2011|pp=192-193}}
<ol>
<li><math>p</math> is continuous;</li>
<li><math>p</math> is continuous at 0;</li>
<li><math>p</math> is uniformly continuous on <math>X</math>;</li>
</ol>
and if <math>p</math> is positive then this list may be extended to include:
<ol start=4>
<li><math>\{x \in X : p(x) < 1\}</math> is open in <math>X.</math></li>
</ol>

If <math>X</math> is a real TVS, <math>f</math> is a linear functional on <math>X,</math> and <math>p</math> is a continuous sublinear function on <math>X,</math> then <math>f \leq p</math> on <math>X</math> implies that <math>f</math> is continuous.{{sfn|Narici|Beckenstein|2011|pp=192-193}}

===Relation to Minkowski functions and open convex sets===

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=
If <math>U</math> is a convex open neighborhood of the origin in a [[topological vector space]] <math>X</math> then the [[Minkowski functional]] of <math>U,</math> <math>p_U : X \to [0, \infty),</math> is a continuous non-negative sublinear function on <math>X</math> such that <math>U = \left\{x \in X : p_U(x) < 1\right\};</math> if in addition <math>U</math> is a [[balanced set]] then <math>p_U</math> is a [[seminorm]] on <math>X.</math>
}}

====Relation to open convex sets====

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=
Suppose that <math>X</math> is a [[topological vector space]] (not necessarily [[Locally convex topological vector space|locally convex]] or [[Hausdorff space|Hausdorff]]) over the real or complex numbers.
Then the open convex subsets of <math>X</math> are exactly those that are of the form <math display=block>z + \{x \in X : p(x) < 1\} = \{x \in X : p(x - z) < 1\}</math> for some <math>z \in X</math> and some positive continuous sublinear function <math>p</math> on <math>X.</math>
}}

{{math proof|proof=
Let <math>V</math> be an open convex subset of <math>X.</math>
If <math>0 \in V</math> then let <math>z := 0</math> and otherwise let <math>z \in V</math> be arbitrary.
Let <math>p : X \to [0, \infty)</math> be the [[Minkowski functional]] of <math>V - z,</math> which is a continuous sublinear function on <math>X</math> since <math>V - z</math> is convex, [[Absorbing set|absorbing]], and open (<math>p</math> however is not necessarily a seminorm since <math>V</math> was not assumed to be [[Balanced set|balanced]]).
From <math>X = X - z,</math> it follows that
<math display=block>z + \{x \in X : p(x) < 1\} = \{x \in X : p(x - z) < 1\}.</math>
It will be shown that <math>V = z + \{x \in X : p(x) < 1\},</math> which will complete the proof.
One of the known [[Minkowski functional#Properties|properties of Minkowski functionals]] guarantees <math display=inline>\{x \in X : p(x) < 1\} = (0, 1)(V - z),</math> where <math>(0, 1)(V - z) \;\stackrel{\scriptscriptstyle\text{def}}{=}\; \{t x : 0 < t < 1, x \in V - z\} = V - z</math> since <math>V - z</math> is convex and contains the origin.
Thus <math>V - z = \{x \in X : p(x) < 1\},</math> as desired. [[Q.E.D.|<math>\blacksquare</math>]]
}}

==Operators==

The concept can be extended to operators that are homogeneous and subadditive.
This requires only that the [[codomain]] be, say, an [[ordered vector space]] to make sense of the conditions.

==Computer science definition==

In [[computer science]], a function <math>f : \Z^+ \to \Reals</math> is called '''sublinear''' if <math>\lim_{n \to \infty} \frac{f(n)}{n} = 0,</math> or <math>f(n) \in o(n)</math> in [[Big O notation#Little-o notation|asymptotic notation]] (notice the small <math>o</math>).
Formally, <math>f(n) \in o(n)</math> if and only if, for any given <math>c > 0,</math> there exists an <math>N</math> such that <math>f(n) < c n</math> for <math>n \geq N.</math><ref>{{cite book|author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]|title=[[Introduction to Algorithms]]|orig-year=1990|edition=2nd|year=2001|publisher=MIT Press and McGraw-Hill|pages=47–48|chapter=3.1|isbn=0-262-03293-7}}</ref>
That is, <math>f</math> grows slower than any linear function.
The two meanings should not be confused: while a Banach functional is [[Convex function|convex]], almost the opposite is true for functions of sublinear growth: every function <math>f(n) \in o(n)</math> can be upper-bounded by a [[concave function]] of sublinear growth.<ref>{{Cite book |title=Groups, graphs, and random walks |isbn=9781316604403 |location=Cambridge |oclc=948670194|last1=Ceccherini-Silberstein|first1=Tullio|last2=Salvatori|first2=Maura|last3=Sava-Huss|first3=Ecaterina|date=2017-06-29|at=Lemma 5.17}}</ref>

==See also==

* {{annotated link|Asymmetric norm}}
* {{annotated link|Auxiliary normed space}}
* {{annotated link|Hahn-Banach theorem}}
* {{annotated link|Linear functional}}
* {{annotated link|Minkowski functional}}
* {{annotated link|Norm (mathematics)}}
* {{annotated link|Seminorm}}
* {{annotated link|Superadditivity}}

==Notes==

{{reflist|group=note}}

'''Proofs'''

{{reflist|group=proof|refs=
<ref group=proof name=SubadditiveSymmetricIsNonnegative>Let <math>x \in X.</math> The triangle inequality and symmetry imply <math>p(0) = p(x + (- x)) \leq p(x) + p(-x) = p(x) + p(x) = 2 p(x).</math> Substituting <math>0</math> for <math>x</math> and then subtracting <math>p(0)</math> from both sides proves that <math>0 \leq p(0).</math> Thus <math>0 \leq p(0) \leq 2 p(x)</math> which implies <math>0 \leq p(x).</math> <math>\blacksquare</math></ref>

<ref group=proof name=NullAtZeroAndSumUpperBound>If <math>x \in X</math> and <math>r := 0</math> then nonnegative homogeneity implies that <math>p(0) = p(r x) = r p(x) = 0 p(x) = 0.</math> Consequently, <math>0 = p(0) = p(x + (-x)) \leq p(x) + p(-x),</math> which is only possible if <math>0 \leq \max \{p(x), p(-x)\}.</math> <math>\blacksquare</math></ref>

<ref group=proof name=ReverseTriangle><math>p(x) = p(y + (x - y)) \leq p(y) + p(x - y),</math> which happens if and only if <math>p(x) - p(y) \leq p(x - y).</math> <math>\blacksquare</math> Substituting <math>y := -x</math> and gives <math>p(x) - p(-x) \leq p(x - (-x)) = p(x + x) \leq p(x) + p(x),</math> which implies <math>- p(-x) \leq p(x)</math> (positive homogeneity is not needed; the triangle inequality suffices). <math>\blacksquare</math></ref>

<ref group=proof name=ConstantOnEquivClasses>Let <math>x \in X</math> and <math>k \in p^{-1}(0) \cap (-p^{-1}(0)).</math> It remains to show that <math>p(x + k) = p(x).</math> The triangle inequality implies <math>p(x + k) \leq p(x) + p(k) = p(x) + 0 = p(x).</math> Since <math>p(-k) = 0,</math> <math>p(x) = p(x) - p(-k) \leq p(x - (-k)) = p(x + k),</math> as desired. <math>\blacksquare</math></ref>
}}

==References==

{{reflist}}

==Bibliography==

* {{Kubrusly The Elements of Operator Theory 2nd Edition 2011}} 
* {{Rudin Walter Functional Analysis|edition=2}} 
* {{Narici Beckenstein Topological Vector Spaces|edition=2}} 
* {{Schaefer Wolff Topological Vector Spaces|edition=2}} 
* {{Schechter Handbook of Analysis and Its Foundations}} 
* {{Trèves François Topological vector spaces, distributions and kernels}} 

{{Functional analysis}}
{{Topological vector spaces}}

[[Category:Articles containing proofs]]
[[Category:Functional analysis]]
[[Category:Linear algebra]]
[[Category:Types of functions]]

Sublinear function - Revision history

imported>Nerdican: /* Definitions */ Replaced erroneous inequality with correct equality