{
  "id": "enwiki-001374573005",
  "slug": "sublinear-function",
  "title": "Sublinear function",
  "qid": "",
  "lead": "In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm, on a vector space is a real-valued function with 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 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 the Hahn-Banach theorem. There is also a different notion in computer science, described below, that also goes by the name \"sublinear function.\"",
  "body": "In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm, on a vector space is a real-valued function with 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 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 the Hahn-Banach theorem. There is also a different notion in computer science, described below, that also goes by the name \"sublinear function.\" ==Definitions== Let X be a vector space over a field \\mathbb{K}, where \\mathbb{K} is either the real numbers \\Reals or complex numbers \\C. A function p \\colon X \\to \\mathbb{R} is called if it has these two properties: Positive homogeneity, that is p(r x) = r p(x) , for all r \\geq 0 and x \\in X . Subadditivity, that is p(x + y) \\leq p(x) + p(y) for x, y \\in X. A function p : X \\to \\Reals 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. It is a if p(-x) = p(x) for all x \\in X. Every subadditive symmetric function is necessarily nonnegative. A sublinear function on a real vector space is symmetric if and only if it is a seminorm. A sublinear function on a real or complex vector space is a seminorm if and only if it is a balanced function or equivalently, if and only if p(u x) \\leq p(x) for every unit length scalar u and x \\in X. The set of all sublinear functions on X, denoted by X^{\\#}, can be partially ordered by declaring p \\leq q if and only if p(x) \\leq q(x) for all x \\in X. A sublinear function is called if it is a minimal element of X^{\\#} under this order. A sublinear function is minimal if and only if it is a real linear functional. ==Examples and sufficient conditions== Every norm, seminorm, and real linear functional is a sublinear function. The identity function on \\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 x \\mapsto -x. More generally, for any real a \\leq b, the map S_{a,b} \\colon \\Reals \\to \\Reals, \\quad x \\mapsto \\begin{cases} a x, & \\text{if } x \\leq 0, \\\\ b x, & \\text{if } x \\geq 0 \\end{cases} is a sublinear function on \\Reals and moreover, every sublinear function p \\colon \\Reals \\to \\Reals is of this form; specifically, if a = -p(-1) and b = p(1) then a \\leq b and p = S_{a, b}. If p and q are sublinear functions on a real vector space X then so is the map x \\mapsto \\max \\{p(x), q(x)\\}. 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, q(x) = \\sup \\{p(x) \\,;\\, p \\in \\mathcal{P}\\}, then q is a sublinear functional on X. A function p \\colon X \\to \\Reals which is subadditive, convex, and satisfies p(0) \\leq 0 is also positively homogeneous (the latter condition p(0) \\leq 0 is necessary as the example of p(x)=\\sqrt{x^2+1} on X=\\mathbb R shows). If p is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming p(0) \\leq 0 , any two properties among subadditivity, convexity, and positive homogeneity implies the third. ==Properties== Every sublinear function is a convex function: For 0 \\leq t \\leq 1, \\begin{alignat}{3} p(t x + (1 - t) y) &\\leq p(t x) + p((1 - t) y) && \\quad\\text{ subadditivity} \\\\ &= t p(x) + (1 - t) p(y) && \\quad\\text{ nonnegative homogeneity} \\\\ \\end{alignat} If p : X \\to \\Reals is a sublinear function on a vector space X then p(0) ~=~ 0 ~\\leq~ p(x) + p(-x), for 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, 0 ~\\leq~ \\max \\{p(x), p(-x)\\}. Moreover, when p : X \\to \\Reals is a sublinear function on a real vector space then the map q : X \\to \\Reals defined by q(x) ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ \\max \\{p(x), p(-x)\\} is a seminorm. Subadditivity of p : X \\to \\Reals guarantees that for all vectors x, y \\in X, p(x) - p(y) ~\\leq~ p(x - y), - p(x) ~\\leq~ p(-x), so if p is also symmetric then the reverse triangle inequality will hold for all vectors x, y \\in X, |p(x) - p(y)| ~\\leq~ p(x - y). Defining \\ker p ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ p^{-1}(0), then subadditivity also guarantees that for all x \\in X, the value of p on the set x + (\\ker p \\cap -\\ker p) = \\{x + k : p(k) = 0 = p(-k)\\} is constant and equal to p(x). In particular, if \\ker p = p^{-1}(0) is a vector subspace of X then - \\ker p = \\ker p and the assignment x + \\ker p \\mapsto p(x), which will be denoted by \\hat{p}, is a well-defined real-valued sublinear function on the quotient space X \\,/\\, \\ker p that satisfies \\hat{p} ^{-1}(0) = \\ker p. If p is a seminorm then \\hat{p} is just the usual canonical norm on the quotient space X \\,/\\, \\ker p. Adding b c to both sides of the hypothesis p(x) + a c \\, (where p(x + a K) ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ \\{p(x + a k) : k \\in K\\} ) and combining that with the conclusion gives p(x) + a c + b c ~ which yields many more inequalities, including, for instance, p(x) + a c + b c ~ in 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). ===Associated seminorm=== If p : X \\to \\Reals 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 q(x) ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ \\max \\{p(x), p(-x)\\} defines a seminorm on the real vector space X called the seminorm associated with p. A sublinear function p on a real or complex vector space is a symmetric function if and only if p = q where q(x) ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ \\max \\{p(x), p(-x)\\} as before. More generally, if p : X \\to \\Reals is a real-valued sublinear function on a (real or complex) vector space X then q(x) ~\\stackrel{\\scriptscriptstyle\\text{def}}{=}~ \\sup_{|u|=1} p(u x) ~=~ \\sup \\{p(u x) : u \\text{ is a unit scalar }\\} will define a seminorm on X if this supremum is always a real number (that is, never equal to \\infty ). ===Relation to linear functionals=== If p is a sublinear function on a real vector space X then the following are equivalent: p is a linear functional. for every x \\in X, p(x) + p(-x) \\leq 0. for every x \\in X, p(x) + p(-x) = 0. p is a minimal sublinear function. If 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. If 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 f^{-1}(1) \\cap \\{x \\in X : p(x) ====Dominating a linear functional==== A 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 f(x) \\leq p(x) for every x that belongs to the domain of f. If f : X \\to \\Reals is a real linear functional on X then f is dominated by p (that is, f \\leq p ) if and only if -p(-x) \\leq f(x) \\leq p(x) \\quad \\text{ for every } x \\in X. Moreover, if p is a seminorm or some other (which by definition means that p(-x) = p(x) holds for all x ) then f \\leq p if and only if |f| \\leq p. ===Continuity=== Suppose X is a topological vector space (TVS) over the real or complex numbers and p is a sublinear function 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 this list may be extended to include: \\{x \\in X : p(x) is open in X. If 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. ===Relation to Minkowski functions and open convex sets=== ====Relation to open convex sets==== {{math proof|proof= Let V be an open convex subset of X. If 0 \\in V then let z := 0 and otherwise let z \\in V be arbitrary. Let p : X \\to [0, \\infty) be the Minkowski functional of V - z, which is a continuous sublinear function on X since V - z is convex, absorbing, and open ( p however is not necessarily a seminorm since V was not assumed to be balanced). From X = X - z, it follows that z + \\{x \\in X : p(x) It will be shown that V = z + \\{x \\in X : p(x) which will complete the proof. One of the known properties of Minkowski functionals guarantees \\{x \\in X : p(x) where (0, 1)(V - z) \\;\\stackrel{\\scriptscriptstyle\\text{def}}{=}\\; \\{t x : 0 since V - z is convex and contains the origin. Thus V - z = \\{x \\in X : p(x) as desired. \\blacksquare }} ==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 f : \\Z^+ \\to \\Reals is called sublinear if \\lim_{n \\to \\infty} \\frac{f(n)}{n} = 0, or f(n) \\in o(n) in asymptotic notation (notice the small o ). Formally, f(n) \\in o(n) if and only if, for any given c > 0, there exists an N such that f(n) for n \\geq N. 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) \\in o(n) can be upper-bounded by a concave function of sublinear growth. ==See also== ==Notes== Proofs ==References== ==Bibliography==",
  "categories": [
    "10639794",
    "22175909",
    "22983403",
    "23060232",
    "23400961",
    "23603337",
    "26220375",
    "29176689",
    "81199107"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374573005",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789242139.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001374573005",
    "type": "webpage",
    "title": "Sublinear function",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/sublinear-function",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          12
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          12
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374573005",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374573005",
    "note": "Immutable snapshot enwiki-001374573005"
  }
}