Sublinear function

In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm or a Banach functional, on a vector space ${\displaystyle X}$ is a real-valued 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 norms, where a seminorm has all the defining properties of a norm 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.^[1]

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

Definitions[]

Let ${\displaystyle X}$ be a vector space over a field ${\displaystyle \mathbb {K} ,}$ where ${\displaystyle \mathbb {K} }$ is either the real numbers ${\displaystyle \mathbb {R} }$ or complex numbers ${\displaystyle \mathbb {C} .}$ A real-valued function ${\displaystyle f:X\to \mathbb {R} }$ on ${\displaystyle X}$ is called a sublinear function (or a sublinear functional if ${\displaystyle \mathbb {K} =\mathbb {R} }$), and also sometimes called a quasi-seminorm or a Banach functional, if it has these two properties:^[1]

1. Positive homogeneity/Nonnegative homogeneity: ${\displaystyle f(rx)=rf(x)}$ for any real ${\displaystyle r\geq 0}$ and any ${\displaystyle x\in X}$; and
2. Subadditivity/Triangle inequality: ${\displaystyle f(x+y)\leq f(x)+f(y)}$ for all ${\displaystyle x,y\in X.}$
   • This subadditivity condition requires ${\displaystyle f}$ to be real-valued.

A sublinear function ${\displaystyle f}$ is called positive^[2] or nonnegative if ${\displaystyle f(x)\geq 0}$ for all ${\displaystyle x\in X.}$

The set of all sublinear functions on ${\displaystyle X,}$ denoted by ${\displaystyle X^{\#},}$ can be partially ordered by declaring ${\displaystyle p\leq q}$ if and only if ${\displaystyle p(x)\leq q(x)}$ for all ${\displaystyle x\in X.}$ A sublinear function is called minimal if it is a minimal element of ${\displaystyle X^{\#}}$ under this order. A sublinear function is minimal if and only if it is a real linear functional.^[1]

Examples and sufficient conditions[]

Every seminorm and norm is a sublinear function and every real linear functional is a sublinear function. The converses are not true in general.

If ${\displaystyle p}$ and ${\displaystyle q}$ are sublinear functions on a real vector space ${\displaystyle X}$ then so is the map ${\displaystyle x\mapsto \max\{p(x),q(x)\}.}$ More generally, if ${\displaystyle {\mathcal {P}}}$ is any non-empty collection of sublinear functionals on a real vector space ${\displaystyle X}$ and if for all ${\displaystyle x\in X,}$ ${\displaystyle q(x):=\sup\{p(x):p\in {\mathcal {P}}\},}$ then ${\displaystyle q}$ is a sublinear functional on ${\displaystyle X.}$^[3]

The linear functional ${\displaystyle x\mapsto -x}$ on ${\displaystyle X=\mathbb {R} }$ is a sublinear functional that is not positive and is not a seminorm.^[3]

Properties[]

Every sublinear function is a convex functional.

If ${\displaystyle p}$ is a real-valued sublinear function on ${\displaystyle X}$ then:

• ${\displaystyle p(0)=0.}$^{[2][proof 1]}
• ${\displaystyle 0\leq p(x)+p(-x)}$ for every ${\displaystyle x\in X.}$^{[proof 2]}
• ${\displaystyle 0\leq \max\{p(x),p(-x)\}}$ for all ${\displaystyle x\in X.}$^[2]
  • The map defined by ${\displaystyle q(x):=\max\{p(x),p(-x)\}}$ is a seminorm on ${\displaystyle X.}$^[2]
  • This implies, in particular, that at least one of ${\displaystyle p(x)}$ and ${\displaystyle p(-x)}$ is non-negative.
• ${\displaystyle p(x)-p(y)\leq p(x-y)}$ for all ${\displaystyle x,y\in X.}$^{[1][proof 3]}

Associated seminorm[]

If ${\displaystyle p}$ is a real-valued sublinear function on ${\displaystyle X}$ then the map ${\displaystyle q(x):=\max\{p(x),p(-x)\}}$ defines a seminorm on ${\displaystyle X}$ called the seminorm associated with ${\displaystyle p.}$^[2]

Relation to linear functions[]

If ${\displaystyle p}$ is a sublinear function on a real vector space ${\displaystyle X}$ then the following are equivalent:^[1]

1. ${\displaystyle p}$ is a linear functional;
2. for every ${\displaystyle x\in X,}$ ${\displaystyle p(x)+p(-x)\leq 0}$;
3. for every ${\displaystyle x\in X,}$ ${\displaystyle p(x)+p(-x)=0}$;
4. ${\displaystyle p}$ is a minimal sublinear function.

If ${\displaystyle p}$ is a sublinear function on a real vector space ${\displaystyle X}$ then there exists a linear functional ${\displaystyle f}$ on ${\displaystyle X}$ such that ${\displaystyle f\leq p.}$^[1]

If ${\displaystyle X}$ is a real vector space, ${\displaystyle f}$ is a linear functional on ${\displaystyle X,}$ and ${\displaystyle p}$ is a positive sublinear function on ${\displaystyle X,}$ then ${\displaystyle f\leq p}$ on ${\displaystyle X}$ if and only if ${\displaystyle f^{-1}(1)\cap \{x\in X:p(x)<1\}=\varnothing .}$^[1]

Continuity[]

Suppose ${\displaystyle X}$ is a topological vector space (TVS) over the real or complex numbers and ${\displaystyle p}$ is a sublinear function on ${\displaystyle X.}$ Then the following are equivalent:^[4]

1. ${\displaystyle p}$ is continuous;
2. ${\displaystyle p}$ is continuous at 0;
3. ${\displaystyle p}$ is uniformly continuous on ${\displaystyle X}$;

and if ${\displaystyle p}$ is positive then we may add to this list:

4. ${\displaystyle \{x\in X:p(x)<1\}}$ is open in ${\displaystyle X.}$

If ${\displaystyle X}$ is a real TVS, ${\displaystyle f}$ is a linear functional on ${\displaystyle X,}$ and ${\displaystyle p}$ is a continuous sublinear function on ${\displaystyle X,}$ then ${\displaystyle f\leq p}$ on ${\displaystyle X}$ implies that ${\displaystyle f}$ is continuous.^[4]

Relation to Minkowski functions and open convex sets[]

Relation to open convex sets

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 ${\displaystyle f:\mathbb {Z} ^{+}\to \mathbb {R} }$ is called sublinear if ${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{n}}=0,}$ or ${\displaystyle f(n)\in o(n)}$ in asymptotic notation (notice the small ${\displaystyle o}$). Formally, ${\displaystyle f(n)\in o(n)}$ if and only if, for any given ${\displaystyle c>0,}$ there exists an ${\displaystyle N}$ such that ${\displaystyle f(n)<cn}$ for ${\displaystyle n\geq N.}$^[5] That is, ${\displaystyle f}$ 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 ${\displaystyle f(n)\in o(n)}$ can be upper-bounded by a concave function of sublinear growth.^[6]

See also[]

• Asymmetric norm – Generalization of the concept of a norm
• Hahn-Banach theorem
• Linear functional
• Norm (mathematics) – Length in a vector space
• Seminorm
• Superadditivity

Notes[]

References[]

Bibliography[]

• ; (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
• Schaefer, Helmut H.; (1999). Topological Vector Spaces. GTM. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.
• Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.