# Sublinear function

In linear algebra, a **sublinear** function (or functional, as is more often used in functional analysis) is a function *f* : *X* → 𝔽 on a vector space *X* over an ordered field 𝔽 (usually the real numbers ℝ or complex numbers ℂ), that satisfies the following properties:

**Positive homogeneity**:*f*(*rx*) =*r f*(*x*) for any positive*r*∈ 𝔽 and any*x*∈*X*; and**Subadditivity**:*f*(*x*+*y*) ≤*f*(*x*) +*f*(*y*) for all*x*,*y*∈*X*.

In functional analysis the name **Banach functional** is used for sublinear functions, especially when formulating Hahn–Banach theorem.

In contrast, in computer science, a function is called **sublinear** if , or *f*(*n*) ∈ *o*(*n*) in asymptotic notation (notice the small ).
Formally, *f*(*n*) ∈ *o*(*n*) if and only if, for any given *c* > 0, there exists an *N* such that *f*(*n*) < *cn* for *n* ≥ *N*.^{[1]}
That is, *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 *f*(*n*) ∈ *o*(*n*) can be upper-bounded by a concave function of sublinear growth.^{[2]}

## DefinitionsEdit

A sublinear functional *f* is called **positive** if *f*(*x*) ≥ 0 for all *x* ∈ *X*.^{[3]}

We partially order the set of all sublinear functionals on *X*, denoted by *X*^{#}, by declaring *p* ≤ *q* if and only if *p*(*x*) ≤ *q*(*x*) for all *x* ∈ *X*.
A sublinear functional is called **minimal** if it is a minimal element of *X*^{#} under this order.
It can be shown a sublinear functional is minimal if and only if it is a linear functional.^{[4]}

## Examples and sufficient conditionsEdit

- Every seminorm and norm is a sublinear function.
- The converse is not true, because (semi-)norms can have their domain vector space over any field (not necessarily ordered) and must have ℝ as their codomain.

- Every linear functional a sublinear function. The converse is not true in general.
- If p and q are sublinear functions on a real vector space X then so is the map
*x*↦ max {*p*(*x*),*q*(*x*) }.- More generally, if 𝒫 is any non-empty collection of sublinear functionals on a real vector space X and if for all
*x*∈*X*,*q*(*x*) := sup {*p*(*x*) :*p*∈ 𝒫 } < ∞, then q is a sublinear functional on X.^{[5]}

- More generally, if 𝒫 is any non-empty collection of sublinear functionals on a real vector space X and if for all

- The linear functional
*x*↦ -*x*on*X*= ℝ is a sublinear functional that is not positive and is not a seminorm.^{[5]}

## PropertiesEdit

If p is a real-valued sublinear functional on X then:

- Every sublinear function is a convex functional.
*p*(0) = 0.^{[3]}- 0 ≤ max {
*p*(*x*),*p*(-*x*) } for all*x*∈*X*.^{[3]}This implies that at least one of*p*(*x*) and*p*(-*x*) is non-negative. *p*(*x*) -*p*(*y*) ≤*p*(*x*-*y*) for all*x*,*y*∈*X*.^{[4]}

### Associated seminormEdit

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

### Relation to linear functionalsEdit

If p is a sublinear functional on a real vector space X then the following are equivalent:^{[4]}

- p is a linear functional;
- for every
*x*∈*X*,*p*(*x*) +*p*(-*x*) ≤ 0; - for every
*x*∈*X*,*p*(*x*) +*p*(-*x*) = 0; - p is a minimal sublinear functional.

If p is a sublinear functional on a real vector space X then there exists a linear functional f on X such that *f* ≤ *p*.^{[4]}

If X is a real vector space, f is a linear functional on X, and p is a sublinear functional on X, then *f* ≤ *p* on X if and only if *f* ^{-1}(1) ∩ { *x* ∈ *X* : *p*(*x*) < 1 } = ∅.^{[4]}

### ContinuityEdit

Suppose X is a TVS over the real or complex numbers and p is a sublinear functional on X. Then the following are equivalent:

- p is continuous;
- p is continuous at 0;
- p is uniformly continuous on X;

and if p is positive then we may add to this list:

- {
*x*∈*X*:*p*(*x*) < 1 } is open in X.

If X is a real TVS, f is a linear functional on X, and p is a continuous sublinear functional on X, then *f* ≤ *p* on X implies that f is continuous.^{[4]}

### Relation to open convex setsEdit

Suppose that X is a TVS (not necessarily locally convex or Hausdorff) over the real or complex numbers.
Then the open convex subsets of X are exactly those that are of the form *z* + { *x* ∈ *X* : *p*(*x*) < 1 } = { *x* ∈ *X* : *p*(*x* - *z*) < 1} for some *z* ∈ *X* and some positive continuous sublinear functional p on X.^{[4]}

## OperatorsEdit

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.

## See alsoEdit

- Hahn-Banach theorem
- Linear functional
- Norm (mathematics) – Length in a vector space
- Seminorm

## ReferencesEdit

**^**Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "3.1".*Introduction to Algorithms*(2nd ed.). MIT Press and McGraw-Hill. pp. 47–48. ISBN 0-262-03293-7.CS1 maint: multiple names: authors list (link)**^**Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29).*Groups, graphs, and random walks*. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.- ^
^{a}^{b}^{c}^{d}Narici 2011, pp. 120-121. - ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Narici 2011, pp. 177-220. - ^
^{a}^{b}Narici 2011, pp. 177-221.

- Narici, Lawrence; Beckenstein, Edward (2011).
*Topological Vector Spaces*. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834. - Schaefer, Helmut H.; Wolff, Manfred P. (1999).
*Topological Vector Spaces*. GTM.**8**(Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.CS1 maint: ref=harv (link) - Trèves, François (August 6, 2006) [1967].
*Topological Vector Spaces, Distributions and Kernels*. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.CS1 maint: ref=harv (link) CS1 maint: date and year (link)

This linear algebra-related article is a stub. You can help Wikipedia by expanding it. |