Sublinear function

{{Short description|Type of function in linear algebra}} In linear algebra, a '''sublinear''' function (or functional as is more often used in functional analysis), also called a '''quasi-seminorm''', on a vector space is a real-valued function with 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 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 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 numbers <math>\Reals</math> or complex numbers <math>\C.</math> A function <math>p \colon X \to \mathbb{R}</math> is called a ''{{em|{{visible anchor|sublinear}}}}'' if it has these two properties:{{sfn|Narici|Beckenstein|2011|pp=177-220}} <ol> <li>Positive homogeneity,{{sfn|Schechter|1996|pp=313-315}} that is <math>p(r x) = r p(x)</math>, for all <math>r \geq 0</math> and <math>x \in X</math>. </li> <li>Subadditivity,{{sfn|Schechter|1996|pp=313-315}} that is <math>p(x + y) \leq p(x) + p(y)</math> for <math>x, y \in X.</math> </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 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> and <math>x \in X.</math>

The set of all sublinear functions on <math>X,</math> denoted by <math>X^{\#},</math> can be 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, seminorm, and real linear functional is a sublinear function. The identity function on <math>\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> S_{a,b} \colon \Reals \to \Reals, \quad x \mapsto \begin{cases} a x, & \text{if } x \leq 0, \\ b x, & \text{if } x \geq 0 \end{cases} </math>

is a sublinear function on <math>\Reals</math> and moreover, every sublinear function <math>p \colon \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 \colon X \to \Reals</math> which is subadditive, 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 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 <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 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 or 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, and open (<math>p</math> however is not necessarily a seminorm since <math>V</math> was not assumed to be 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 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. <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 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, 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==

'''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==

==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}}

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