{"history":[],"article":{"id":"304d80cd-c04c-47ac-90bf-f86f5405070d","title":"Sublinear function","slug":"sublinear-function","content":":::summary\n:::\n\n# \nIn [linear algebra](https://bliptext.com/articles/linear-algebra), a **sublinear** [function](https://bliptext.com/articles/function-mathematics) (or [functional](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics) as is more often used in [functional](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics) analysis), also called a **quasi-[seminorm](https://bliptext.com/articles/seminorm)** or a **Banach [functional](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics)**, on a [vector space](https://bliptext.com/articles/vector-space) X is a [real](https://bliptext.com/articles/real-number)-valued [function](https://bliptext.com/articles/function-mathematics) with only some of the properties of a [seminorm](https://bliptext.com/articles/seminorm).\nUnlike seminorms, a sublinear function does not have to be [nonnegative](https://bliptext.com/articles/nonnegative)-valued and also does not have to be [absolutely homogeneous](https://bliptext.com/articles/absolutely-homogeneous).\nSemi[norms](https://bliptext.com/articles/norm-mathematics) are themselves abstractions of the more well known notion of [norms](https://bliptext.com/articles/norm-mathematics), where a seminorm has all the defining properties of a norm that it is not required to map non-zero vectors to non-zero values.\nIn [functional analysis](https://bliptext.com/articles/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](https://bliptext.com/articles/hahn-banach-theorem).\nThe notion of a sublinear function was introduced by [Stefan Banach](https://bliptext.com/articles/stefan-banach) when he proved his version of the [Hahn-Banach theorem](https://bliptext.com/articles/hahn-banach-theorem).\nThere is also a different notion in [computer science](https://bliptext.com/articles/computer-science), described below, that also goes by the name \"sublinear function.\"\n\n# Definitions\nLet X be a [vector space](https://bliptext.com/articles/vector-space) over a field \\mathbb{K}, where \\mathbb{K} is either the [real numbers](https://bliptext.com/articles/real-number) \\Reals or [complex numbers](https://bliptext.com/articles/complex-number) \\C.\nA real-valued function on X is called a **' (or a '** if ), and also sometimes called a **' or a '**, if it has these two properties:\n

[Positive homogeneity](https://bliptext.com/articles/positive-homogeneity)****/****[Nonnegative homogeneity](https://bliptext.com/articles/nonnegative-homogeneity): for all real r \\geq 0 and all x \\in X.
[Subadditivity](https://bliptext.com/articles/subadditivity)****/****[Triangle inequality](https://bliptext.com/articles/triangle-inequality): for all x, y \\in X. <****/****ol>\nA function is called or if p(x) \\geq 0 for all x \\in X, although some authors define to instead mean that p(x) \\neq 0 whenever x \\neq 0; these definitions are not equivalent.\nIt is a if for all x \\in X. Every subadditive symmetric function is necessarily nonnegative.\nA sublinear function on a real vector space is [symmetric](https://bliptext.com/articles/) if and only if it is a [seminorm](https://bliptext.com/articles/seminorm).\nA sublinear function on a real or complex vector space is a seminorm if and only if it is a [balanced function](https://bliptext.com/articles/balanced-function) or equivalently, if and only if for every [unit length](https://bliptext.com/articles/unit-length) scalar u (satisfying |u| = 1) and every x \\in X.\nThe set of all sublinear functions on X, denoted by X^{\\#}, can be [partially ordered](https://bliptext.com/articles/partial-order) by declaring p \\leq q if and only if for all x \\in X. A sublinear function is called if it is a [minimal element](https://bliptext.com/articles/minimal-element) of X^{\\#} under this order.\nA sublinear function is minimal if and only if it is a real [linear functional](https://bliptext.com/articles/linear-functional).\n\n# Examples and sufficient conditions\nEvery [norm](https://bliptext.com/articles/norm-mathematics), semi[norm](https://bliptext.com/articles/norm-mathematics), and real linear functional is a sublinear function.\nThe [identity function](https://bliptext.com/articles/identity-function) on X := \\Reals 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\nMore generally, for any real a \\leq b, the map\nis a sublinear function on X := \\Reals and moreover, every sublinear function is of this form; specifically, if and b := p(1) then a \\leq b and\nIf p and q are sublinear functions on a real vector space X then so is the map More generally, if \\mathcal{P} is any non-empty collection of sublinear functionals on a real vector space X and if for all x \\in X, then q is a sublinear functional on X.\nA function which is [subadditive](https://bliptext.com/articles/subadditivity), [convex](https://bliptext.com/articles/convex-function), and satisfies p(0) \\leq 0 is also positively homogeneous (the latter condition p(0) \\leq 0 is necessary as the example of on shows).\nIf p is positively homogeneous, it is convex if and only if it is subadditive.\nTherefore, assuming p(0) \\leq 0, any two properties among subadditivity, convexity, and positive homogeneity implies the third.\n\n# Properties\nEvery sublinear function is a [convex function](https://bliptext.com/articles/convex-function): For\nIf is a sublinear function on a vector space X then\nfor every x \\in X, which implies that at least one of p(x) and p(-x) must be nonnegative; that is, for every x \\in X,\nMoreover, when is a sublinear function on a real vector space then the map defined by is a seminorm.\nSubadditivity of guarantees that for all vectors x, y \\in X,\nso if p is also [symmetric](https://bliptext.com/articles/) then the [reverse triangle inequality](https://bliptext.com/articles/reverse-triangle-inequality) will hold for all vectors x, y \\in X,\nDefining then subadditivity also guarantees that for all x \\in X, the value of p on the set is constant and equal to p(x).\nIn particular, if is a vector subspace of X then and the assignment which will be denoted by \\hat{p}, is a well-defined real-valued sublinear function on the [quotient space](https://bliptext.com/articles/quotient-space-linear-algebra) that satisfies If p is a seminorm then \\hat{p} is just the usual canonical norm on the [quotient space](https://bliptext.com/articles/quotient-space-linear-algebra)\nAdding b c to both sides of the hypothesis (where ) and combining that with the conclusion gives\nwhich yields many more inequalities, including, for instance,\nin which an expression on one side of a strict inequality \\,<\\, can be obtained from the other by replacing the symbol c with \\mathbf{z} (or vice versa) and moving the closing parenthesis to the right (or left) of an adjacent summand (all other symbols remain fixed and unchanged).\n\n## Associated seminorm\nIf is a real-valued sublinear function on a real vector space X (or if X is complex, then when it is considered as a real vector space) then the map defines a [seminorm](https://bliptext.com/articles/seminorm) on the real vector space X called the **[seminorm](https://bliptext.com/articles/seminorm) associated with p.**\nA sublinear function p on a real or complex vector space is a [symmetric function](https://bliptext.com/articles/) if and only if p = q where as before.\nMore generally, if is a real-valued sublinear function on a (real or complex) vector space X then\nwill define a [seminorm](https://bliptext.com/articles/seminorm) on X if this supremum is always a real number (that is, never equal to \\infty).\n\n## Relation to linear functionals\nIf p is a sublinear function on a real vector space X then the following are equivalent:\n
1. p is a [linear functional](https://bliptext.com/articles/linear-functional).
2. for every x \\in X,
3. for every x \\in X,
4. p is a minimal sublinear function.
\nIf p is a sublinear function on a real vector space X then there exists a linear functional f on X such that f \\leq p.\nIf X is a real vector space, f is a linear functional on X, and p is a positive sublinear function on X, then f \\leq p on X if and only if\n\n### Dominating a linear functional\nA real-valued function f defined on a subset of a real or complex vector space X is said to be a sublinear function p if for every x that belongs to the domain of f. If is a real [linear functional](https://bliptext.com/articles/linear-functional) on X then f is dominated by p (that is, f \\leq p) if and only if Moreover, if p is a seminorm or some other (which by definition means that holds for all x) then f \\leq p if and only if |f| \\leq p.\n\n## Continuity\nSuppose X is a [topological vector space](https://bliptext.com/articles/topological-vector-space) (TVS) over the real or complex numbers and p is a sublinear function on X. Then the following are equivalent:\n
1. p is continuous;
2. p is continuous at 0;
3. p is uniformly continuous on X;
\nand if p is positive then this list may be extended to include:\n
is open in X.

\nIf X is a real TVS, f is a linear functional on X, and p is a continuous sublinear function on X, then f \\leq p on X implies that f is continuous.\n\n## Relation to Minkowski functions and open convex sets\n\n### Relation to open convex sets\n\n# Operators\nThe concept can be extended to operators that are homogeneous and subadditive.\nThis requires only that the [codomain](https://bliptext.com/articles/codomain) be, say, an [ordered vector space](https://bliptext.com/articles/ordered-vector-space) to make sense of the conditions.\n\n# Computer science definition\nIn [computer science](https://bliptext.com/articles/computer-science), a function is called **sublinear** if or in [asymptotic notation](https://bliptext.com/articles/big-o-notation) (notice the small o).\nFormally, if and only if, for any given c > 0, there exists an N such that f(n) < c n for n \\geq N. That is, f grows slower than any linear function.\nThe two meanings should not be confused: while a Banach functional is [convex](https://bliptext.com/articles/convex-function), almost the opposite is true for functions of sublinear growth: every function can be upper-bounded by a [concave function](https://bliptext.com/articles/concave-function) of sublinear growth.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:36:09.918Z","updated_at":"2025-01-25T21:36:09.918Z","search_vector":"'function':2 'sublinear':1","search_content":" \n \n\n# \nIn [linear algebra](https://bliptext.com/articles/linear-algebra), a **sublinear** [function](https://bliptext.com/articles/function-mathematics) (or [[function](https://bliptext.com/articles/function-mathematics)al](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics) as is more often used in [[function](https://bliptext.com/articles/function-mathematics)al](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics) analysis), also called a **quasi-[seminorm](https://bliptext.com/articles/seminorm)** or a **Banach [[function](https://bliptext.com/articles/function-mathematics)al](https://bliptext.com/articles/[function](https://bliptext.com/articles/function-mathematics)al-mathematics)**, on a [vector space](https://bliptext.com/articles/vector-space) X is a [real](https://bliptext.com/articles/real-number)-valued [function](https://bliptext.com/articles/function-mathematics) with only some of the properties of a [seminorm](https://bliptext.com/articles/seminorm).\nUnlike seminorms, a sublinear function does not have to be [nonnegative](https://bliptext.com/articles/nonnegative)-valued and also does not have to be [absolutely homogeneous](https://bliptext.com/articles/absolutely-homogeneous).\nSemi[norms](https://bliptext.com/articles/norm-mathematics) are themselves abstractions of the more well known notion of [norms](https://bliptext.com/articles/norm-mathematics), where a seminorm has all the defining properties of a norm that it is not required to map non-zero vectors to non-zero values.\nIn [functional analysis](https://bliptext.com/articles/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](https://bliptext.com/articles/hahn-banach-theorem).\nThe notion of a sublinear function was introduced by [Stefan Banach](https://bliptext.com/articles/stefan-banach) when he proved his version of the [Hahn-Banach theorem](https://bliptext.com/articles/hahn-banach-theorem).\nThere is also a different notion in [computer science](https://bliptext.com/articles/computer-science), described below, that also goes by the name \"sublinear function.\"\n\n# Definitions\nLet X be a [vector space](https://bliptext.com/articles/vector-space) over a field \\mathbb{K}, where \\mathbb{K} is either the [real numbers](https://bliptext.com/articles/real-number) \\Reals or [complex numbers](https://bliptext.com/articles/complex-number) \\C.\nA real-valued function on X is called a **' (or a '** if ), and also sometimes called a **' or a '**, if it has these two properties:\n \n [Positive homogeneity](https://bliptext.com/articles/positive-homogeneity)****/****[Nonnegative homogeneity](https://bliptext.com/articles/nonnegative-homogeneity): for all real r \\geq 0 and all x \\in X. [Subadditivity](https://bliptext.com/articles/subadditivity)****/****[Triangle inequality](https://bliptext.com/articles/triangle-inequality): for all x, y \\in X. \nA function is called or if p(x) \\geq 0 for all x \\in X, although some authors define to instead mean that p(x) \\neq 0 whenever x \\neq 0; these definitions are not equivalent.\nIt is a if for all x \\in X. Every subadditive symmetric function is necessarily nonnegative.\nA sublinear function on a real vector space is [symmetric](https://bliptext.com/articles/) if and only if it is a [seminorm](https://bliptext.com/articles/seminorm).\nA sublinear function on a real or complex vector space is a seminorm if and only if it is a [balanced function](https://bliptext.com/articles/balanced-function) or equivalently, if and only if for every [unit length](https://bliptext.com/articles/unit-length) scalar u (satisfying |u| = 1) and every x \\in X.\nThe set of all sublinear functions on X, denoted by X^{\\#}, can be [partially ordered](https://bliptext.com/articles/partial-order) by declaring p \\leq q if and only if for all x \\in X. A sublinear function is called if it is a [minimal element](https://bliptext.com/articles/minimal-element) of X^{\\#} under this order.\nA sublinear function is minimal if and only if it is a real [linear functional](https://bliptext.com/articles/linear-functional).\n\n# Examples and sufficient conditions\nEvery [norm](https://bliptext.com/articles/norm-mathematics), semi[norm](https://bliptext.com/articles/norm-mathematics), and real linear functional is a sublinear function.\nThe [identity function](https://bliptext.com/articles/identity-function) on X := \\Reals 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\nMore generally, for any real a \\leq b, the map\nis a sublinear function on X := \\Reals and moreover, every sublinear function is of this form; specifically, if and b := p(1) then a \\leq b and\nIf p and q are sublinear functions on a real vector space X then so is the map More generally, if \\mathcal{P} is any non-empty collection of sublinear functionals on a real vector space X and if for all x \\in X, then q is a sublinear functional on X.\nA function which is [subadditive](https://bliptext.com/articles/subadditivity), [convex](https://bliptext.com/articles/convex-function), and satisfies p(0) \\leq 0 is also positively homogeneous (the latter condition p(0) \\leq 0 is necessary as the example of on shows).\nIf p is positively homogeneous, it is convex if and only if it is subadditive.\nTherefore, assuming p(0) \\leq 0, any two properties among subadditivity, convexity, and positive homogeneity implies the third.\n\n# Properties\nEvery sublinear function is a [convex function](https://bliptext.com/articles/convex-function): For\nIf is a sublinear function on a vector space X then\nfor every x \\in X, which implies that at least one of p(x) and p(-x) must be nonnegative; that is, for every x \\in X,\nMoreover, when is a sublinear function on a real vector space then the map defined by is a seminorm.\nSubadditivity of guarantees that for all vectors x, y \\in X,\nso if p is also [symmetric](https://bliptext.com/articles/) then the [reverse triangle inequality](https://bliptext.com/articles/reverse-triangle-inequality) will hold for all vectors x, y \\in X,\nDefining then subadditivity also guarantees that for all x \\in X, the value of p on the set is constant and equal to p(x).\nIn particular, if is a vector subspace of X then and the assignment which will be denoted by \\hat{p}, is a well-defined real-valued sublinear function on the [quotient space](https://bliptext.com/articles/quotient-space-linear-algebra) that satisfies If p is a seminorm then \\hat{p} is just the usual canonical norm on the [quotient space](https://bliptext.com/articles/quotient-space-linear-algebra)\nAdding b c to both sides of the hypothesis (where ) and combining that with the conclusion gives\nwhich yields many more inequalities, including, for instance,\nin which an expression on one side of a strict inequality \\, \n p is a [linear functional](https://bliptext.com/articles/linear-functional). \n for every x \\in X, \n for every x \\in X, \n p is a minimal sublinear function. \n \nIf p is a sublinear function on a real vector space X then there exists a linear functional f on X such that f \\leq p.\nIf X is a real vector space, f is a linear functional on X, and p is a positive sublinear function on X, then f \\leq p on X if and only if\n\n### Dominating a linear functional\nA real-valued function f defined on a subset of a real or complex vector space X is said to be a sublinear function p if for every x that belongs to the domain of f. If is a real [linear functional](https://bliptext.com/articles/linear-functional) on X then f is dominated by p (that is, f \\leq p) if and only if Moreover, if p is a seminorm or some other (which by definition means that holds for all x) then f \\leq p if and only if |f| \\leq p.\n\n## Continuity\nSuppose X is a [topological vector space](https://bliptext.com/articles/topological-vector-space) (TVS) over the real or complex numbers and p is a sublinear function on X. Then the following are equivalent:\n \n p is continuous; \n p is continuous at 0; \n p is uniformly continuous on X; \n \nand if p is positive then this list may be extended to include:\n is open in X. \n \nIf X is a real TVS, f is a linear functional on X, and p is a continuous sublinear function on X, then f \\leq p on X implies that f is continuous.\n\n## Relation to Minkowski functions and open convex sets\n\n### Relation to open convex sets\n\n# Operators\nThe concept can be extended to operators that are homogeneous and subadditive.\nThis requires only that the [codomain](https://bliptext.com/articles/codomain) be, say, an [ordered vector space](https://bliptext.com/articles/ordered-vector-space) to make sense of the conditions.\n\n# Computer science definition\nIn [computer science](https://bliptext.com/articles/computer-science), a function is called **sublinear** if or in [asymptotic notation](https://bliptext.com/articles/big-o-notation) (notice the small o).\nFormally, if and only if, for any given c > 0, there exists an N such that f(n) < c n for n \\geq N. That is, f grows slower than any linear function.\nThe two meanings should not be confused: while a Banach functional is [convex](https://bliptext.com/articles/convex-function), almost the opposite is true for functions of sublinear growth: every function can be upper-bounded by a [concave function](https://bliptext.com/articles/concave-function) of sublinear growth.","revisionCount":0},"hasMore":false,"nextCursor":null}

History