Sublinear function

In linear algebra, a sublinear function (or functional as is more often used in functional analysis) or a quasi-seminorm, on a vector space X over an ordered field 𝔽, where 𝔽 is either the real numbers ℝ or complex numbers ℂ, is a real-valued function f : X → ℝ that satisfies the following properties:[1]

1. Positive homogeneity/Nonnegative homogeneity: f (r x) = r f (x) for any real r ≥ 0 and any x ∈ X; and
2. Subadditivity/Triangle inequality: f (x + y) ≤ f (x) + f (y) for all x, y ∈ X.
   • This condition requires f to be real-valued.

In functional analysis the name Banach functional is sometimes used for sublinear functions, especially when formulating 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

A sublinear functional f is called positive if f(x) ≥ 0 for all x ∈ X.[2]

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.[1]

Examples and sufficient conditions

• 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.[3]

• The linear functional x ↦ -x on X = ℝ is a sublinear functional that is not positive and is not a seminorm.[3]

Properties

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

• Every sublinear function is a convex functional.
• p(0) = 0.[2]
• 0 ≤ max {p(x), p(-x) } for all x ∈ X.[2]
  • The map defined by q (x) := max {p(x), p(-x)} is a seminorm on X.[2]
  • This implies, in particular, 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.[1]

Associated seminorm

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.[2]

Relation to linear functionals

If p is a sublinear functional on a real vector space X then the following are equivalent:[1]

1. p is a linear functional;
2. for every x ∈ X, p(x) + p(-x) ≤ 0;
3. for every x ∈ X, p(x) + p(-x) = 0;
4. 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.[1]

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 } = ∅.[1]

Continuity

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

1. p is continuous;
2. p is continuous at 0;
3. p is uniformly continuous on X;

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

4. { 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.[1]

Relation to open convex sets

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.[1]

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 f(n) ∈ o(n) in asymptotic notation (notice the small ${\displaystyle o}$). 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.[4] 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.[5]

See also

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

References

1. Narici 2011, pp. 177-220. sfn error: no target: CITEREFNarici2011 (help)
2. Narici 2011, pp. 120-121. sfn error: no target: CITEREFNarici2011 (help)
3. Narici 2011, pp. 177-221. sfn error: no target: CITEREFNarici2011 (help)
4. 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)
5. Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.

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