Sublinear function: Difference between revisions

Revision as of 23:50, 30 January 2023

Revision as of 23:51, 30 January 2023

Line 8:

==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>\RReals</math> or [[complex number]]s <math>\C.</math>

A real-valued function <math>p : X \to \RReals</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} = \RReals</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>

Line 17:

</ol>

A function <math>p : X \to \RReals</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>

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

Line 30:

Every [[Norm (mathematics)|norm]], [[seminorm]], and real linear functional is a sublinear function.

The [[identity function]] <math>\RReals \to \RReals</math> on <math>X := \RReals</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} :\;&& \RReals &&\;\to \;& \RReals \\[0.3ex]

&& x &&\;\mapsto\;&

\begin{cases}

Line 40:

\end{cases} \\

\end{alignat}</math>

is a sublinear function on <math>X := \RReals</math> and moreover, every sublinear function <math>p : \RReals \to \RReals</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 \RReals</math> is sublinear if and only if it is [[Subadditivity|subadditive]], [[Convex function|convex]], and satisfies <math>p(0) \leq 0.</math>

==Properties==

Line 56:

</math>

If <math>p : X \to \RReals</math> is a sublinear function on a vector space <math>X</math> then<ref group=proof>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>{{sfn|Narici|Beckenstein|2011|pp=120-121}}

<math display=block>p(0) ~=~ 0 ~\leq~ p(x) + p(- x) \qquad \text{ for every } 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,{{sfn|Narici|Beckenstein|2011|pp=120-121}}

<math display=block>0 ~\leq~ \max \{p(x), p(- x)\} \qquad \text{ for every } x \in X.</math>

Moreover, when <math>p : X \to \RReals</math> is a sublinear function on a real vector space then the map <math>q : X \to \RReals</math> defined by <math>q(x) := \max \{p(x), p(- x)\}</math> is a seminorm.{{sfn|Narici|Beckenstein|2011|pp=120-121}}

Subadditivity of <math>p : X \to \RReals</math> guarantees that for all vectors <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> 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>

<math display=block>p(x) - p(y) ~\leq~ p(x - y),</math>

<math display=block>- p(x) ~\leq~ p(- x),</math>

Line 88:

===Associated seminorm===

If <math>p : X \to \RReals</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) := \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) := \max \{p(x), p(- x)\}</math> as before.

More generally, if <math>p : X \to \RReals</math> is a real-valued sublinear function on a (real or complex) vector space <math>X</math> then

<math display=block>q(x) ~:=~ \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>).

Line 112:

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 \RReals</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 \RReals</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.

}}

Line 123:

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

Suppose <math>f : X \to \RReals</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.

Line 173:

==Computer science definition==

In [[computer science]], a function <math>f : \Z^+ \to \RReals</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.