Sublinear function: Difference between revisions

Revision as of 01:26, 13 January 2022

Revision as of 01:43, 13 January 2022

Line 17:

A function <math>f : X \to \R</math> is called ''{{em|{{visible anchor|positive}}}}''{{sfn|Narici|Beckenstein|2011|pp=120-121}} or ''{{em|{{visible anchor|nonnegative}}}}'' if <math>f(x) \geq 0</math> for all <math>x \in X.</math>

It is calleda ''{{em|{{visible anchor|symmetric function}}}}'' if <math>f(-x) = f(x)</math> for all <math>x \in X.</math>

Every subadditive symmetric function is necessarily nonnegative.<ref group=proof>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>

Every subadditive symmetric function is necessarily nonnegative.

A sublinear function on a real vector space is [[#symmetric function|symmetric]] if and only if it is a [[seminorm]].

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>

Line 25:

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 [[seminorm]] and [[Norm (mathematics)|norm]] is a sublinear function and every real linear functional is a sublinear function. The converses are not true in general.

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

The linear functional <math>x \mapsto -x</math> on <math>X = \R</math> is a sublinear functional that is not positive and is not a seminorm.{{sfn|Narici|Beckenstein|2011|pp=177-221}}

== Properties ==

Every sublinear function is a [[Convex function|convex]] [[Functional (mathematics)|functional]].

Line 40:

<ul>

<li><math>p(0) = 0.</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}<ref group=proof>UsingIf <math>rx :=\in 0X</math> and any <math>xr \in:= X,0</math> non-negativethen nonnegative homogeneity implies that <math>p(0) = p(r x) = r p(x) = 0 p(x) = 0.</math> <math>\blacksquare</math></ref></li>

<li><math>0 \leq p(x) + p(- x)</math> for every <math>x \in X.</math><ref group=proof><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></li>

<li><math>0 \leq \max \{ p(x), p(- x) \}</math> for all <math>x \in X.</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}

* The map defined by <math>q(x) := \max \{ p(x), p(- x) \}</math> is a seminorm on <math>X.</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}

* This implies, in particular, that at least one of <math>p(x)</math> and <math>p(- x)</math> is non-negative.</li>

<li><math>p(x) - p(y) \leq p(x - y)</math> for all <math>x, y \in X.</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}<ref group=proof><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></ref></li>

</ul>

=== Associated seminorm ===

If <math>p</math> is a real-valued sublinear function on a real vector space <math>X</math> then the map <math>q(x) := \max \{ p(x), p(- x) \}</math> defines a [[seminorm]] on <math>X</math> called the '''seminorm associated with <math>p.</math>'''{{sfn|Narici|Beckenstein|2011|pp=120-121}}

The sublinear function <math>p</math> is a [[#symmetric function|symmetric function]] if and only if <math>q = p.</math>

=== Relation to linear functions 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}}

Line 77 ⟶ 78:

}}

=== Continuity ===

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=

Line 83 ⟶ 84:

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>

}}

Line 96 ⟶ 97:

and if <math>p</math> is positive then we may add to this list:

<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 TVS <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 [[Balanced set|balanced]] 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=

Line 120 ⟶ 121:

Let <math>p : X \to [0, \infty)</math> be the [[Minkowski functional]] of <math>V - z</math> where <math>p</math> 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 the properties of Minkowski functionals, it is known that <math>V - z = \{x \in X : p(x) < 1\}</math> from which

<math>V = z + \{ x \in X : p(x) < 1 \}</math> follows. Since <math>z + \{x \in X : p(x) < 1\} = \{x \in X : p(x - z) < 1\},</math> this completes the proof. <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 \R</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>).

Line 135 ⟶ 136:

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

Line 145 ⟶ 146:

* {{annotated link|Superadditivity}}

== Notes ==

{{reflist|group=note}}

{{reflist|group=proof}}

== References ==

{{reflist}}