fbpx
Wikipedia

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

There is also a different notion in computer science, described below, that also goes by the name "sublinear function."

Definitions edit

Let   be a vector space over a field   where   is either the real numbers   or complex numbers   A real-valued function   on   is called a sublinear function (or a sublinear functional if  ), and also sometimes called a quasi-seminorm or a Banach functional, if it has these two properties:[1]

  1. Positive homogeneity/Nonnegative homogeneity:[2]   for all real   and all  
    • This condition holds if and only if   for all positive real   and all  
  2. Subadditivity/Triangle inequality:[2]   for all  
    • This subadditivity condition requires   to be real-valued.

A function   is called positive[3] or nonnegative if   for all   although some authors[4] define positive to instead mean that   whenever   these definitions are not equivalent. It is a symmetric function if   for all   Every subadditive symmetric function is necessarily nonnegative.[proof 1] 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   for every unit length scalar   (satisfying  ) and every  

The set of all sublinear functions on   denoted by   can be partially ordered by declaring   if and only if   for all   A sublinear function is called minimal if it is a minimal element of   under this order. A sublinear function is minimal if and only if it is a real linear functional.[1]

Examples and sufficient conditions edit

Every norm, seminorm, and real linear functional is a sublinear function. The identity function   on   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  [5] More generally, for any real   the map

 
is a sublinear function on   and moreover, every sublinear function   is of this form; specifically, if   and   then   and  

If   and   are sublinear functions on a real vector space   then so is the map   More generally, if   is any non-empty collection of sublinear functionals on a real vector space   and if for all     then   is a sublinear functional on  [5]


A function   which is subadditive, convex, and satisfies   is also positively homogeneous (the latter condition   is necessary as the example of   on   shows). If   is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming  , any two properties among subadditivity, convexity, and positive homogeneity implies the third.

Properties edit

Every sublinear function is a convex function: For  

 

If   is a sublinear function on a vector space   then[proof 2][3]

 
for every   which implies that at least one of   and   must be nonnegative; that is, for every  [3]
 
Moreover, when   is a sublinear function on a real vector space then the map   defined by   is a seminorm.[3]

Subadditivity of   guarantees that for all vectors  [1][proof 3]

 
 
so if   is also symmetric then the reverse triangle inequality will hold for all vectors  
 

Defining   then subadditivity also guarantees that for all   the value of   on the set   is constant and equal to  [proof 4] In particular, if   is a vector subspace of   then   and the assignment   which will be denoted by   is a well-defined real-valued sublinear function on the quotient space   that satisfies   If   is a seminorm then   is just the usual canonical norm on the quotient space  

Pryce's sublinearity lemma[2] — Suppose   is a sublinear functional on a vector space   and that   is a non-empty convex subset. If   is a vector and   are positive real numbers such that

 
then for every positive real   there exists some   such that
 

Adding   to both sides of the hypothesis   (where  ) and combining that with the conclusion gives

 
which yields many more inequalities, including, for instance,
 
in which an expression on one side of a strict inequality   can be obtained from the other by replacing the symbol   with   (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 edit

If   is a real-valued sublinear function on a real vector space   (or if   is complex, then when it is considered as a real vector space) then the map   defines a seminorm on the real vector space   called the seminorm associated with  [3] A sublinear function   on a real or complex vector space is a symmetric function if and only if   where   as before.

More generally, if   is a real-valued sublinear function on a (real or complex) vector space   then

 
will define a seminorm on   if this supremum is always a real number (that is, never equal to  ).

Relation to linear functionals edit

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

  1.   is a linear functional.
  2. for every    
  3. for every    
  4.   is a minimal sublinear function.

If   is a sublinear function on a real vector space   then there exists a linear functional   on   such that  [1]

If   is a real vector space,   is a linear functional on   and   is a positive sublinear function on   then   on   if and only if  [1]

Dominating a linear functional edit

A real-valued function   defined on a subset of a real or complex vector space   is said to be dominated by a sublinear function   if   for every   that belongs to the domain of   If   is a real linear functional on   then[6][1]   is dominated by   (that is,  ) if and only if

 
Moreover, if   is a seminorm or some other symmetric map (which by definition means that   holds for all  ) then   if and only if  

Theorem[1] — If   be a sublinear function on a real vector space   and if   then there exists a linear functional   on   that is dominated by   (that is,  ) and satisfies   Moreover, if   is a topological vector space and   is continuous at the origin then   is continuous.

Continuity edit

Theorem[7] — Suppose   is a subadditive function (that is,   for all  ). Then   is continuous at the origin if and only if   is uniformly continuous on   If   satisfies   then   is continuous if and only if its absolute value   is continuous. If   is non-negative then   is continuous if and only if   is open in  

Suppose   is a topological vector space (TVS) over the real or complex numbers and   is a sublinear function on   Then the following are equivalent:[7]

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

and if   is positive then this list may be extended to include:

  1.   is open in  

If   is a real TVS,   is a linear functional on   and   is a continuous sublinear function on   then   on   implies that   is continuous.[7]

Relation to Minkowski functions and open convex sets edit

Theorem[7] — If   is a convex open neighborhood of the origin in a topological vector space   then the Minkowski functional of     is a continuous non-negative sublinear function on   such that   if in addition   is a balanced set then   is a seminorm on  

Relation to open convex sets edit

Theorem[7] — Suppose that   is a topological vector space (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of   are exactly those that are of the form

 
for some   and some positive continuous sublinear function   on  
Proof

Let   be an open convex subset of   If   then let   and otherwise let   be arbitrary. Let   be the Minkowski functional of   which is a continuous sublinear function on   since   is convex, absorbing, and open (  however is not necessarily a seminorm since   was not assumed to be balanced). From   it follows that

 
It will be shown that   which will complete the proof. One of the known properties of Minkowski functionals guarantees   where   since   is convex and contains the origin. Thus   as desired.  

Operators edit

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 edit

In computer science, a function   is called sublinear if   or   in asymptotic notation (notice the small  ). Formally,   if and only if, for any given   there exists an   such that   for  [8] That is,   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   can be upper-bounded by a concave function of sublinear growth.[9]

See also edit

Notes edit

Proofs

  1. ^ Let   The triangle inequality and symmetry imply   Substituting   for   and then subtracting   from both sides proves that   Thus   which implies    
  2. ^ If   and   then nonnegative homogeneity implies that   Consequently,   which is only possible if    
  3. ^   which happens if and only if     Substituting   and gives   which implies   (positive homogeneity is not needed; the triangle inequality suffices).  
  4. ^ Let   and   It remains to show that   The triangle inequality implies   Since     as desired.  

References edit

  1. ^ a b c d e f g h i Narici & Beckenstein 2011, pp. 177–220.
  2. ^ a b c Schechter 1996, pp. 313–315.
  3. ^ a b c d e Narici & Beckenstein 2011, pp. 120–121.
  4. ^ Kubrusly 2011, p. 200.
  5. ^ a b Narici & Beckenstein 2011, pp. 177–221.
  6. ^ Rudin 1991, pp. 56–62.
  7. ^ a b c d e Narici & Beckenstein 2011, pp. 192–193.
  8. ^ 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.{{cite book}}: CS1 maint: multiple names: authors list (link)
  9. ^ Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.{{cite book}}: CS1 maint: location missing publisher (link)

Bibliography edit

sublinear, function, linear, algebra, sublinear, function, functional, more, often, used, functional, analysis, also, called, quasi, seminorm, banach, functional, vector, space, displaystyle, real, valued, function, with, only, some, properties, seminorm, unli. 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 X displaystyle X 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 except 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 1 There is also a different notion in computer science described below that also goes by the name sublinear function Contents 1 Definitions 2 Examples and sufficient conditions 3 Properties 3 1 Associated seminorm 3 2 Relation to linear functionals 3 2 1 Dominating a linear functional 3 3 Continuity 3 4 Relation to Minkowski functions and open convex sets 3 4 1 Relation to open convex sets 4 Operators 5 Computer science definition 6 See also 7 Notes 8 References 9 BibliographyDefinitions editLet X displaystyle X nbsp be a vector space over a field K displaystyle mathbb K nbsp where K displaystyle mathbb K nbsp is either the real numbers R displaystyle mathbb R nbsp or complex numbers C displaystyle mathbb C nbsp A real valued function p X R displaystyle p X to mathbb R nbsp on X displaystyle X nbsp is called a sublinear function or a sublinear functional if K R displaystyle mathbb K mathbb R nbsp and also sometimes called a quasi seminorm or a Banach functional if it has these two properties 1 Positive homogeneity Nonnegative homogeneity 2 p r x r p x displaystyle p rx rp x nbsp for all real r 0 displaystyle r geq 0 nbsp and all x X displaystyle x in X nbsp This condition holds if and only if p r x r p x displaystyle p rx leq rp x nbsp for all positive real r gt 0 displaystyle r gt 0 nbsp and all x X displaystyle x in X nbsp Subadditivity Triangle inequality 2 p x y p x p y displaystyle p x y leq p x p y nbsp for all x y X displaystyle x y in X nbsp This subadditivity condition requires p displaystyle p nbsp to be real valued A function p X R displaystyle p X to mathbb R nbsp is called positive 3 or nonnegative if p x 0 displaystyle p x geq 0 nbsp for all x X displaystyle x in X nbsp although some authors 4 define positive to instead mean that p x 0 displaystyle p x neq 0 nbsp whenever x 0 displaystyle x neq 0 nbsp these definitions are not equivalent It is a symmetric function if p x p x displaystyle p x p x nbsp for all x X displaystyle x in X nbsp Every subadditive symmetric function is necessarily nonnegative proof 1 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 p x displaystyle p ux leq p x nbsp for every unit length scalar u displaystyle u nbsp satisfying u 1 displaystyle u 1 nbsp and every x X displaystyle x in X nbsp The set of all sublinear functions on X displaystyle X nbsp denoted by X displaystyle X nbsp can be partially ordered by declaring p q displaystyle p leq q nbsp if and only if p x q x displaystyle p x leq q x nbsp for all x X displaystyle x in X nbsp A sublinear function is called minimal if it is a minimal element of X displaystyle X nbsp under this order A sublinear function is minimal if and only if it is a real linear functional 1 Examples and sufficient conditions editEvery norm seminorm and real linear functional is a sublinear function The identity function R R displaystyle mathbb R to mathbb R nbsp on X R displaystyle X mathbb R nbsp 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 x displaystyle x mapsto x nbsp 5 More generally for any real a b displaystyle a leq b nbsp the mapS a b R R x a x if x 0 b x if x 0 displaystyle begin alignedat 4 S a b amp amp mathbb R amp amp to amp mathbb R 0 3ex amp amp x amp amp mapsto amp begin cases ax amp text if x leq 0 bx amp text if x geq 0 end cases end alignedat nbsp is a sublinear function on X R displaystyle X mathbb R nbsp and moreover every sublinear function p R R displaystyle p mathbb R to mathbb R nbsp is of this form specifically if a p 1 displaystyle a p 1 nbsp and b p 1 displaystyle b p 1 nbsp then a b displaystyle a leq b nbsp and p S a b displaystyle p S a b nbsp If p displaystyle p nbsp and q displaystyle q nbsp are sublinear functions on a real vector space X displaystyle X nbsp then so is the map x max p x q x displaystyle x mapsto max p x q x nbsp More generally if P displaystyle mathcal P nbsp is any non empty collection of sublinear functionals on a real vector space X displaystyle X nbsp and if for all x X displaystyle x in X nbsp q x sup p x p P displaystyle q x sup p x p in mathcal P nbsp then q displaystyle q nbsp is a sublinear functional on X displaystyle X nbsp 5 A function p X R displaystyle p X to mathbb R nbsp which is subadditive convex and satisfies p 0 0 displaystyle p 0 leq 0 nbsp is also positively homogeneous the latter condition p 0 0 displaystyle p 0 leq 0 nbsp is necessary as the example of p x x 2 1 displaystyle p x sqrt x 2 1 nbsp on X R displaystyle X mathbb R nbsp shows If p displaystyle p nbsp is positively homogeneous it is convex if and only if it is subadditive Therefore assuming p 0 0 displaystyle p 0 leq 0 nbsp any two properties among subadditivity convexity and positive homogeneity implies the third Properties editEvery sublinear function is a convex function For 0 t 1 displaystyle 0 leq t leq 1 nbsp p t x 1 t y p t x p 1 t y subadditivity t p x 1 t p y nonnegative homogeneity displaystyle begin alignedat 3 p tx 1 t y amp leq p tx p 1 t y amp amp quad text subadditivity amp tp x 1 t p y amp amp quad text nonnegative homogeneity end alignedat nbsp If p X R displaystyle p X to mathbb R nbsp is a sublinear function on a vector space X displaystyle X nbsp then proof 2 3 p 0 0 p x p x displaystyle p 0 0 leq p x p x nbsp for every x X displaystyle x in X nbsp which implies that at least one of p x displaystyle p x nbsp and p x displaystyle p x nbsp must be nonnegative that is for every x X displaystyle x in X nbsp 3 0 max p x p x displaystyle 0 leq max p x p x nbsp Moreover when p X R displaystyle p X to mathbb R nbsp is a sublinear function on a real vector space then the map q X R displaystyle q X to mathbb R nbsp defined by q x def max p x p x displaystyle q x stackrel scriptscriptstyle text def max p x p x nbsp is a seminorm 3 Subadditivity of p X R displaystyle p X to mathbb R nbsp guarantees that for all vectors x y X displaystyle x y in X nbsp 1 proof 3 p x p y p x y displaystyle p x p y leq p x y nbsp p x p x displaystyle p x leq p x nbsp so if p displaystyle p nbsp is also symmetric then the reverse triangle inequality will hold for all vectors x y X displaystyle x y in X nbsp p x p y p x y displaystyle p x p y leq p x y nbsp Defining ker p def p 1 0 displaystyle ker p stackrel scriptscriptstyle text def p 1 0 nbsp then subadditivity also guarantees that for all x X displaystyle x in X nbsp the value of p displaystyle p nbsp on the set x ker p ker p x k p k 0 p k displaystyle x ker p cap ker p x k p k 0 p k nbsp is constant and equal to p x displaystyle p x nbsp proof 4 In particular if ker p p 1 0 displaystyle ker p p 1 0 nbsp is a vector subspace of X displaystyle X nbsp then ker p ker p displaystyle ker p ker p nbsp and the assignment x ker p p x displaystyle x ker p mapsto p x nbsp which will be denoted by p displaystyle hat p nbsp is a well defined real valued sublinear function on the quotient space X ker p displaystyle X ker p nbsp that satisfies p 1 0 ker p displaystyle hat p 1 0 ker p nbsp If p displaystyle p nbsp is a seminorm then p displaystyle hat p nbsp is just the usual canonical norm on the quotient space X ker p displaystyle X ker p nbsp Pryce s sublinearity lemma 2 Suppose p X R displaystyle p X to mathbb R nbsp is a sublinear functional on a vector space X displaystyle X nbsp and that K X displaystyle K subseteq X nbsp is a non empty convex subset If x X displaystyle x in X nbsp is a vector and a c gt 0 displaystyle a c gt 0 nbsp are positive real numbers such thatp x a c lt inf k K p x a k displaystyle p x ac lt inf k in K p x ak nbsp then for every positive real b gt 0 displaystyle b gt 0 nbsp there exists some z K displaystyle mathbf z in K nbsp such that p x a z b c lt inf k K p x a z b k displaystyle p x a mathbf z bc lt inf k in K p x a mathbf z bk nbsp Adding b c displaystyle bc nbsp to both sides of the hypothesis p x a c lt inf p x a K textstyle p x ac lt inf p x aK nbsp where p x a K def p x a k k K displaystyle p x aK stackrel scriptscriptstyle text def p x ak k in K nbsp and combining that with the conclusion givesp x a c b c lt inf p x a K b c p x a z b c lt inf p x a z b K displaystyle p x ac bc lt inf p x aK bc leq p x a mathbf z bc lt inf p x a mathbf z bK nbsp which yields many more inequalities including for instance p x a c b c lt p x a z b c lt p x a z b z displaystyle p x ac bc lt p x a mathbf z bc lt p x a mathbf z b mathbf z nbsp in which an expression on one side of a strict inequality lt displaystyle lt nbsp can be obtained from the other by replacing the symbol c displaystyle c nbsp with z displaystyle mathbf z nbsp 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 edit If p X R displaystyle p X to mathbb R nbsp is a real valued sublinear function on a real vector space X displaystyle X nbsp or if X displaystyle X nbsp is complex then when it is considered as a real vector space then the map q x def max p x p x displaystyle q x stackrel scriptscriptstyle text def max p x p x nbsp defines a seminorm on the real vector space X displaystyle X nbsp called the seminorm associated with p displaystyle p nbsp 3 A sublinear function p displaystyle p nbsp on a real or complex vector space is a symmetric function if and only if p q displaystyle p q nbsp where q x def max p x p x displaystyle q x stackrel scriptscriptstyle text def max p x p x nbsp as before More generally if p X R displaystyle p X to mathbb R nbsp is a real valued sublinear function on a real or complex vector space X displaystyle X nbsp thenq x def sup u 1 p u x sup p u x u is a unit scalar displaystyle q x stackrel scriptscriptstyle text def sup u 1 p ux sup p ux u text is a unit scalar nbsp will define a seminorm on X displaystyle X nbsp if this supremum is always a real number that is never equal to displaystyle infty nbsp Relation to linear functionals edit If p displaystyle p nbsp is a sublinear function on a real vector space X displaystyle X nbsp then the following are equivalent 1 p displaystyle p nbsp is a linear functional for every x X displaystyle x in X nbsp p x p x 0 displaystyle p x p x leq 0 nbsp for every x X displaystyle x in X nbsp p x p x 0 displaystyle p x p x 0 nbsp p displaystyle p nbsp is a minimal sublinear function If p displaystyle p nbsp is a sublinear function on a real vector space X displaystyle X nbsp then there exists a linear functional f displaystyle f nbsp on X displaystyle X nbsp such that f p displaystyle f leq p nbsp 1 If X displaystyle X nbsp is a real vector space f displaystyle f nbsp is a linear functional on X displaystyle X nbsp and p displaystyle p nbsp is a positive sublinear function on X displaystyle X nbsp then f p displaystyle f leq p nbsp on X displaystyle X nbsp if and only if f 1 1 x X p x lt 1 displaystyle f 1 1 cap x in X p x lt 1 varnothing nbsp 1 Dominating a linear functional edit A real valued function f displaystyle f nbsp defined on a subset of a real or complex vector space X displaystyle X nbsp is said to be dominated by a sublinear function p displaystyle p nbsp if f x p x displaystyle f x leq p x nbsp for every x displaystyle x nbsp that belongs to the domain of f displaystyle f nbsp If f X R displaystyle f X to mathbb R nbsp is a real linear functional on X displaystyle X nbsp then 6 1 f displaystyle f nbsp is dominated by p displaystyle p nbsp that is f p displaystyle f leq p nbsp if and only if p x f x p x for every x X displaystyle p x leq f x leq p x quad text for every x in X nbsp Moreover if p displaystyle p nbsp is a seminorm or some other symmetric map which by definition means that p x p x displaystyle p x p x nbsp holds for all x displaystyle x nbsp then f p displaystyle f leq p nbsp if and only if f p displaystyle f leq p nbsp Theorem 1 If p X R displaystyle p X to mathbb R nbsp be a sublinear function on a real vector space X displaystyle X nbsp and if z X displaystyle z in X nbsp then there exists a linear functional f displaystyle f nbsp on X displaystyle X nbsp that is dominated by p displaystyle p nbsp that is f p displaystyle f leq p nbsp and satisfies f z p z displaystyle f z p z nbsp Moreover if X displaystyle X nbsp is a topological vector space and p displaystyle p nbsp is continuous at the origin then f displaystyle f nbsp is continuous Continuity edit Theorem 7 Suppose f X R displaystyle f X to mathbb R nbsp is a subadditive function that is f x y f x f y displaystyle f x y leq f x f y nbsp for all x y X displaystyle x y in X nbsp Then f displaystyle f nbsp is continuous at the origin if and only if f displaystyle f nbsp is uniformly continuous on X displaystyle X nbsp If f displaystyle f nbsp satisfies f 0 0 displaystyle f 0 0 nbsp then f displaystyle f nbsp is continuous if and only if its absolute value f X 0 displaystyle f X to 0 infty nbsp is continuous If f displaystyle f nbsp is non negative then f displaystyle f nbsp is continuous if and only if x X f x lt 1 displaystyle x in X f x lt 1 nbsp is open in X displaystyle X nbsp Suppose X displaystyle X nbsp is a topological vector space TVS over the real or complex numbers and p displaystyle p nbsp is a sublinear function on X displaystyle X nbsp Then the following are equivalent 7 p displaystyle p nbsp is continuous p displaystyle p nbsp is continuous at 0 p displaystyle p nbsp is uniformly continuous on X displaystyle X nbsp and if p displaystyle p nbsp is positive then this list may be extended to include x X p x lt 1 displaystyle x in X p x lt 1 nbsp is open in X displaystyle X nbsp If X displaystyle X nbsp is a real TVS f displaystyle f nbsp is a linear functional on X displaystyle X nbsp and p displaystyle p nbsp is a continuous sublinear function on X displaystyle X nbsp then f p displaystyle f leq p nbsp on X displaystyle X nbsp implies that f displaystyle f nbsp is continuous 7 Relation to Minkowski functions and open convex sets edit Theorem 7 If U displaystyle U nbsp is a convex open neighborhood of the origin in a topological vector space X displaystyle X nbsp then the Minkowski functional of U displaystyle U nbsp p U X 0 displaystyle p U X to 0 infty nbsp is a continuous non negative sublinear function on X displaystyle X nbsp such that U x X p U x lt 1 displaystyle U left x in X p U x lt 1 right nbsp if in addition U displaystyle U nbsp is a balanced set then p U displaystyle p U nbsp is a seminorm on X displaystyle X nbsp Relation to open convex sets edit Theorem 7 Suppose that X displaystyle X nbsp is a topological vector space not necessarily locally convex or Hausdorff over the real or complex numbers Then the open convex subsets of X displaystyle X nbsp are exactly those that are of the formz x X p x lt 1 x X p x z lt 1 displaystyle z x in X p x lt 1 x in X p x z lt 1 nbsp for some z X displaystyle z in X nbsp and some positive continuous sublinear function p displaystyle p nbsp on X displaystyle X nbsp Proof Let V displaystyle V nbsp be an open convex subset of X displaystyle X nbsp If 0 V displaystyle 0 in V nbsp then let z 0 displaystyle z 0 nbsp and otherwise let z V displaystyle z in V nbsp be arbitrary Let p X 0 displaystyle p X to 0 infty nbsp be the Minkowski functional of V z displaystyle V z nbsp which is a continuous sublinear function on X displaystyle X nbsp since V z displaystyle V z nbsp is convex absorbing and open p displaystyle p nbsp however is not necessarily a seminorm since V displaystyle V nbsp was not assumed to be balanced From X X z displaystyle X X z nbsp it follows thatz x X p x lt 1 x X p x z lt 1 displaystyle z x in X p x lt 1 x in X p x z lt 1 nbsp It will be shown that V z x X p x lt 1 displaystyle V z x in X p x lt 1 nbsp which will complete the proof One of the known properties of Minkowski functionals guarantees x X p x lt 1 0 1 V z textstyle x in X p x lt 1 0 1 V z nbsp where 0 1 V z def t x 0 lt t lt 1 x V z V z displaystyle 0 1 V z stackrel scriptscriptstyle text def tx 0 lt t lt 1 x in V z V z nbsp since V z displaystyle V z nbsp is convex and contains the origin Thus V z x X p x lt 1 displaystyle V z x in X p x lt 1 nbsp as desired displaystyle blacksquare nbsp Operators editThe 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 editIn computer science a function f Z R displaystyle f mathbb Z to mathbb R nbsp is called sublinear if lim n f n n 0 displaystyle lim n to infty frac f n n 0 nbsp or f n o n displaystyle f n in o n nbsp in asymptotic notation notice the small o displaystyle o nbsp Formally f n o n displaystyle f n in o n nbsp if and only if for any given c gt 0 displaystyle c gt 0 nbsp there exists an N displaystyle N nbsp such that f n lt c n displaystyle f n lt cn nbsp for n N displaystyle n geq N nbsp 8 That is f displaystyle f nbsp 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 displaystyle f n in o n nbsp can be upper bounded by a concave function of sublinear growth 9 See also editAsymmetric norm Generalization of the concept of a norm Auxiliary normed space Hahn Banach theorem Theorem on extension of bounded linear functionalsPages displaying short descriptions of redirect targets Linear functional Linear map from a vector space to its field of scalarsPages displaying short descriptions of redirect targets Minkowski functional Function made from a set Norm mathematics Length in a vector space Seminorm nonnegative real valued function on a real or complex vector space that satisfies the triangle inequality and is absolutely homogenousPages displaying wikidata descriptions as a fallback SuperadditivityNotes editProofs Let x X displaystyle x in X nbsp The triangle inequality and symmetry imply p 0 p x x p x p x p x p x 2 p x displaystyle p 0 p x x leq p x p x p x p x 2p x nbsp Substituting 0 displaystyle 0 nbsp for x displaystyle x nbsp and then subtracting p 0 displaystyle p 0 nbsp from both sides proves that 0 p 0 displaystyle 0 leq p 0 nbsp Thus 0 p 0 2 p x displaystyle 0 leq p 0 leq 2p x nbsp which implies 0 p x displaystyle 0 leq p x nbsp displaystyle blacksquare nbsp If x X displaystyle x in X nbsp and r 0 displaystyle r 0 nbsp then nonnegative homogeneity implies that p 0 p r x r p x 0 p x 0 displaystyle p 0 p rx rp x 0p x 0 nbsp Consequently 0 p 0 p x x p x p x displaystyle 0 p 0 p x x leq p x p x nbsp which is only possible if 0 max p x p x displaystyle 0 leq max p x p x nbsp displaystyle blacksquare nbsp p x p y x y p y p x y displaystyle p x p y x y leq p y p x y nbsp which happens if and only if p x p y p x y displaystyle p x p y leq p x y nbsp displaystyle blacksquare nbsp Substituting y x displaystyle y x nbsp and gives p x p x p x x p x x p x p x displaystyle p x p x leq p x x p x x leq p x p x nbsp which implies p x p x displaystyle p x leq p x nbsp positive homogeneity is not needed the triangle inequality suffices displaystyle blacksquare nbsp Let x X displaystyle x in X nbsp and k p 1 0 p 1 0 displaystyle k in p 1 0 cap p 1 0 nbsp It remains to show that p x k p x displaystyle p x k p x nbsp The triangle inequality implies p x k p x p k p x 0 p x displaystyle p x k leq p x p k p x 0 p x nbsp Since p k 0 displaystyle p k 0 nbsp p x p x p k p x k p x k displaystyle p x p x p k leq p x k p x k nbsp as desired displaystyle blacksquare nbsp References edit a b c d e f g h i Narici amp Beckenstein 2011 pp 177 220 a b c Schechter 1996 pp 313 315 a b c d e Narici amp Beckenstein 2011 pp 120 121 Kubrusly 2011 p 200 a b Narici amp Beckenstein 2011 pp 177 221 Rudin 1991 pp 56 62 a b c d e Narici amp Beckenstein 2011 pp 192 193 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 a href Template Cite book html title Template Cite book cite book a 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 href Template Cite book html title Template Cite book cite book a CS1 maint location missing publisher link Bibliography editKubrusly Carlos S 2011 The Elements of Operator Theory Second ed Boston Birkhauser ISBN 978 0 8176 4998 2 OCLC 710154895 Rudin Walter 1991 Functional Analysis International Series in Pure and Applied Mathematics Vol 8 Second ed New York NY McGraw Hill Science Engineering Math ISBN 978 0 07 054236 5 OCLC 21163277 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 Vol 8 Second ed New York NY Springer New York Imprint Springer ISBN 978 1 4612 7155 0 OCLC 840278135 Schechter Eric 1996 Handbook of Analysis and Its Foundations San Diego CA Academic Press ISBN 978 0 12 622760 4 OCLC 175294365 Treves Francois 2006 1967 Topological Vector Spaces Distributions and Kernels Mineola N Y Dover Publications ISBN 978 0 486 45352 1 OCLC 853623322 Retrieved from https en wikipedia org w index php title Sublinear function amp oldid 1186968338, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.