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 formula_1 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 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. There is also a different notion in computer science, described below, that also goes by the name "sublinear function." Definitions. Let formula_1 be a vector space over a field formula_3 where formula_4 is either the real numbers formula_5 or complex numbers formula_6 A real-valued function formula_7 on  formula_1 is called a ' (or a ' if formula_9), and also sometimes called a ' or a ', if it has these two properties: A function formula_7 is called ' or ' if formula_11 for all formula_12 It is a " if formula_13 for all formula_12 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. The set of all sublinear functions on formula_15 denoted by formula_16 can be partially ordered by declaring formula_17 if and only if formula_18 for all formula_12 A sublinear function is called " if it is a  minimal element of formula_20 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 formula_21 on formula_22 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 formula_23 More generally, for any real formula_24 the map formula_25 is a sublinear function on formula_22 and moreover, every sublinear function formula_27 is of this form ; specifically, if formula_28 and formula_29 then formula_30 and formula_31 If formula_32 and formula_33 are sublinear functions on a real vector space formula_1 then so is the map formula_35 More generally, if formula_36 is any non-empty collection of sublinear functionals on a real vector space formula_1 and if for all formula_38 formula_39 then formula_33 is a sublinear functional on formula_41 A function formula_7 is sublinear if and only if it is subadditive, convex, and satisfies formula_43 Properties. Every sublinear function is a convex function. If formula_7 is a sublinear function on a vector space formula_1 then formula_46 which implies that  at least one of formula_47 and formula_48 must be nonnegative; that is, formula_49 Moreover, when formula_7 is a sublinear function on a real vector space then the map formula_51 defined by formula_52 is a seminorm. Subadditivity of formula_7 guarantees formula_54 so if formula_32 is also symmetric then the reverse triangle inequality will hold: formula_56 Associated seminorm. If formula_7 is a real-valued sublinear function on a real vector space formula_1 (or if formula_1 is complex, then when it is considered as a real vector space) then the map formula_52 defines a seminorm on the real vector space formula_1 called the  seminorm associated with formula_62 A sublinear function formula_32 on a real or complex vector space is a symmetric function if and only if formula_64 where formula_52 as before. More generally, if formula_7 is a real-valued sublinear function on a (real or complex) vector space formula_1 then formula_68 will define a seminorm on formula_1 if this supremum is always a real number (that is, never equal to formula_70). Relation to linear functionals. If formula_32 is a sublinear function on a real vector space formula_1 then the following are equivalent: If formula_32 is a sublinear function on a real vector space  formula_1 then there exists a linear functional formula_75 on formula_1 such that formula_77 If formula_1 is a real vector space, formula_75 is a linear functional on formula_15 and formula_32 is a positive sublinear function on formula_15 then formula_83 on formula_1 if and only if formula_85 Dominating a linear functional. A real-valued function formula_75 defined on a subset of a real or complex vector space formula_1 is said to be a sublinear function formula_32 if formula_89 for every formula_90 that belongs to the domain of formula_91 If formula_92 is a real linear functional on formula_1 then formula_75 is dominated by  formula_32 (that is, formula_83) if and only if formula_97 Moreover, if formula_32 is a seminorm or some other (which by definition means that formula_13 holds for all formula_90) then formula_83 if and only if formula_102 Continuity. Suppose formula_1 is a topological vector space (TVS) over the real or complex numbers and formula_32 is a sublinear function on formula_41 Then the following are equivalent: and if formula_32 is positive then we may add to this list: If formula_1 is a real TVS, formula_75 is a linear functional on formula_15 and formula_32 is a continuous sublinear function on formula_15 then formula_83 on  formula_1 implies that formula_75 is continuous. 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 formula_115 is called sublinear if formula_116 or formula_117 in asymptotic notation (notice the small formula_118). Formally, formula_117 if and only if, for any given formula_120 there exists an formula_121 such that formula_122 for formula_123 That is, formula_75 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 formula_117 can be upper-bounded by a concave function of sublinear growth.