Function Repository Resource:

ConvexDefectRatio

Source Notebook

Compute the normalized fragmentation measure of a subset relative to its order-convex closure

Contributed by: E. Chan-López, A. Martín-Ruiz and Carlos Antonio Marín Mendoza

ResourceFunction["ConvexDefectRatio"][subset,parentSet]

returns the normalized convex defect ratio , defined as the proportion of elements of parentSet lying in Interval[MinMax[subset]] that are not contained in subset.

Details and Options

ResourceFunction["ConvexDefectRatio"][subset,parentSet] computes .
Returns a real number in .
Returns 0 for the empty set and for order-convex subsets.
A value of 0 for δ(S, P) indicates that the subset is order-convex within parentSet.
Values closer to 1 indicate increasing fragmentation relative to the convex hull.
Computed in a single pass.
The interval induced by the subset is constructed via Select. The ratio is obtained without explicitly forming intermediate defect or closure objects.
Satisfies .
The option "ComparisonFunction" accepts any binary comparison function. The default is LessEqual. Non-numeric elements (strings, symbols) fall back to canonical ordering automatically.
Applicable only to finite totally ordered sets.
Elements must support comparison via LessEqual or a custom comparison function.
Does not verify that subset is contained in parent set.
Returns a machine-precision real number (via N).
For exact arithmetic, compute the ratio explicitly as the quotient of integer counts over the induced interval.

Examples

Basic Examples (4) 

Non-convex subset. The ratio measures the missing fraction of the convex hull:

In[1]:=
ResourceFunction["ConvexDefectRatio"][{1, 3, 7, 9}, Range[10]]
Out[1]=

A convex set has ratio zero:

In[2]:=
ResourceFunction["ConvexDefectRatio"][{3, 4, 5}, Range[10]]
Out[2]=

Maximum fragmentation. Only boundary points remain:

In[3]:=
ResourceFunction["ConvexDefectRatio"][{1, 100}, Range[100]]
Out[3]=

The empty set returns zero:

In[4]:=
ResourceFunction["ConvexDefectRatio"][{}, Range[50]]
Out[4]=

Scope (3) 

Works with rational elements:

In[5]:=
ResourceFunction[
 "ConvexDefectRatio"][{1/4, 3/4}, {0, 1/4, 1/2, 3/4, 1}]
Out[5]=

Works with strings under canonical (lexicographic) order:

In[6]:=
ResourceFunction[
 "ConvexDefectRatio"][{"b", "f"}, {"a", "b", "c", "d", "e", "f"}]
Out[6]=

A singleton always has ratio zero:

In[7]:=
ResourceFunction["ConvexDefectRatio"][{5}, Range[10]]
Out[7]=

Options (2) 

The default value of "ComparisonFunction" is LessEqual:

In[8]:=
Options[
ResourceFunction["ConvexDefectRatio"]]
Out[8]=

A custom comparison function can redefine the ordering. Under the standard order 1< 2<3<4<5, the subset {1, 4} has defect ratio 0.5 because the elements 2 and 3 lie between 1 and 4:

In[9]:=
parentSet = {1, 2, 3, 4, 5};
In[10]:=
subset = {1, 4};
In[11]:=
ResourceFunction["ConvexDefectRatio"][subset, parentSet]
Out[11]=

With the custom ordering , the element 4 is the immediate successor of 1, so the interval contains only , meaning that the defect vanishes:

In[12]:=
customOrd[Pattern[a, 
Blank[]], Pattern[b, 
Blank[]]] := Module[{order = {1, 4, 2, 5, 3}},
   	LessEqual[Part[Position[order, a], 1, 1],
    		Part[Position[order, b], 1, 1]
    	]
   ];
In[13]:=
ResourceFunction["ConvexDefectRatio"][subset, parentSet, "ComparisonFunction" -> customOrd]
Out[13]=

Default ordering. Closure of is . Two gaps. Ratio .

Custom ordering. Closure of is . Ratio 0.

Te comparison function defines the interval.

Applications (2) 

Convexity phase diagram of the logistic map

Measure the fragmentation of the logistic attractor as a function of the parameter :

In[14]:=
With[{grid = Range[0., 1., 0.005]},
 	ListLinePlot[
  		Table[
   			Module[{orbit, disc},
    				orbit = Part[
      					NestList[Function[r * # * (1 - #)], 0.2, 2000],
      					500 ;;
      				];
    				disc = DeleteDuplicates @ Round[orbit, 0.005];
    				{r, ResourceFunction["ConvexDefectRatio"][disc, grid]}
    			],
   			{r, 2.5, 4., 0.005}
   		],
  		PlotRange -> All, AxesLabel -> {"r", "\[Delta](S, P)"},
  		PlotLabel -> "Convexity Phase Diagram of the Logistic Map", Filling -> Bottom
  	]
 ]
Out[14]=

For , the attractor is a fixed point and . Through the period-doubling cascade, the ratio increases as the orbit spreads into disjoint bands. The sharp dips correspond to periodic windows — intervals of stability where the orbit collapses onto a finite cycle, yielding only a few points within a wide convex hull. At , the map is conjugate to the full tent map and the orbit becomes dense in at the chosen resolution, driving .

Prime gap fragmentation

The primes become maximally non-convex as , reflecting the Prime Number Theorem ( since ):

In[15]:=
ListLinePlot[
 	Table[{n, ResourceFunction["ConvexDefectRatio"][Prime @ Range @ PrimePi @ n, Range @ n]},
  		{n, 10, 1000, 10}
  	],
 	AxesLabel -> {"n", "\[Delta]"},
 	PlotLabel -> "Prime Gap Fragmentation"
 ]
Out[15]=

The curve increases toward 1. By the Prime Number Theorem, , so the fraction of integers that are prime within the convex hull tends to zero. Accordingly, the defect ratio approaches unity, providing a quantitative expression of the increasing sparsity of primes among the integers.

Properties and Relations (5) 

The ratio is zero if and only if OrderConvexQ returns True:

In[16]:=
With[{s = {2, 3, 5}, p = Range @ 10},
 	SameQ[ResourceFunction["OrderConvexQ"][s, p],
  		Equal[ResourceFunction["ConvexDefectRatio"][s, p], 0]
  	]
 ]
Out[16]=

Equivalent to the fraction of elements in the induced interval that are not contained in the subset:

In[17]:=
With[{s = {1, 5, 9}, p = Range @ 10},
 	SameQ[ResourceFunction["ConvexDefectRatio"][s, p],
  		N[
   			Divide[
    				Length[
     					Select[p,
      						Function[
       							And[LessEqual[Min @ s, #, Max @ s], ! MemberQ[s, #]]
       						]
      					]
     				],
    				Length[Select[p, LessEqual[Min @ s, #, Max @ s] &]]
    			]
   		]
  	]
 ]
Out[17]=

The ratio equals one minus the density of the subset within its induced interval:

In[18]:=
With[{s = {1, 4, 9}, p = Range @ 10},
 	SameQ[ResourceFunction["ConvexDefectRatio"][s, p],
  		Subtract[1,
   			N[
    				Length[s] / Length[Select[p, LessEqual[Min[s], #, Max @ s] &]]
    			]
   		]
  	]
 ]
Out[18]=

Monotonicity. Adding elements to the subset can only decrease or preserve the ratio:

In[19]:=
With[
 	{
  		p = Range @ 20,
  		a = {2, 18},
  		b = {2, 10, 18}
  	},
 	LessEqual[ResourceFunction["ConvexDefectRatio"][b, p], ResourceFunction["ConvexDefectRatio"][a, p]]
 ]
Out[19]=

A subset containing all elements of its induced interval has ratio zero:

In[20]:=
With[{s = {2, 8}, p = Range @ 10},
 	ResourceFunction["ConvexDefectRatio"][
  Select[p, LessEqual[Min @ s, #, Max @ s] &], p]
 ]
Out[20]=

Possible Issues (1) 

Numerical precision. The result is a machine-precision real. Small rounding differences may occur compared to exact rational arithmetic. Invalid containment. If subset is not contained in parent set, the ratio may exceed 1. The result is a machine-precision real, not an exact rational number:

In[21]:=
Head[ResourceFunction["ConvexDefectRatio"][{1, 5}, Range[10]]]
Out[21]=

Neat Examples (2) 

Track the defect ratio of a random walk orbit on as it explores its range over time. The ratio starts at zero (a single visited point is trivially convex), spikes as gaps appear, and eventually decays back toward zero once the walk covers every site in its range. This is a discrete analogue of the cover time on a path graph:

In[22]:=
SeedRandom @ 42;
Module[{walk, grid, data},
 	grid = Range @ 50;
 	walk = Clip[
   Accumulate @ Prepend[RandomChoice[{-2, -1, 1, 2}, 100], 25],
   		{1, 50}
   	];
 	data = Table[{t, ResourceFunction["ConvexDefectRatio"][
     DeleteDuplicates[walk[[1 ;; t]]], grid]},
   		{t, 1, 101}
   	];
 	ListLinePlot[data,
  		AxesLabel -> {"t", "\[Delta]"},
  		PlotLabel -> "Defect Ratio of Random Walk Orbit",
  		PlotRange -> {{0, 110}, {0, 26/100}},
  		Filling -> Bottom
  	]
 ]
Out[23]=

Compare the defect ratio across three qualitatively different dynamical regimes of the logistic map: fixed point, period-doubling, and full chaos, evaluated at representative parameter values:

In[24]:=
With[{grid = Range[0., 1., 0.001]},
 	TableForm[
  		Table[
   			Module[{orbit, disc},
    				orbit = Part[
      					NestList[Function[r * # * (1 - #)], 0.2, 10000],
      					500 ;;
      				];
    				disc = DeleteDuplicates @ Round[orbit, 0.001];
    				{r, Length @ disc, ResourceFunction["ConvexDefectRatio"][disc, grid]}
    			],
   			{r, {2.8, 3.2, 3.56, 3.83, 3.99, 4.}}
   		],
  		TableHeadings -> {None, {"r", "|orbit|", "\[Delta]"}}
  	]
 ]
Out[24]=

The table reveals the nonmonotonic signature of the route to chaos: increases through the period-doubling cascade (), peaks inside periodic windows (e.g. , where the orbit collapses onto a low-period cycle), and returns toward zero as the attractor becomes increasingly dense, approaching full support at . The small residual value at is a finite-orbit artifact: the invariant density

is minimal near , so this region is sampled least frequently, and the last grid points to be visited lie in that neighborhood.

Publisher

Ramón Eduardo Chan López

Version History

  • 1.0.0 – 03 April 2026

Source Metadata

Related Resources

Author Notes

ConvexDefectRatio provides a normalized measure of deviation from order-convexity within a finite totally ordered set. The function assumes that parent set defines the ambient order and that elements admit comparison via LessEqual or a custom ordering. By expressing the defect relative to the size of the induced interval, it enables meaningful comparisons across subsets of different scales. It is particularly useful in discretized settings where relative coverage, rather than absolute gap count, is of interest, such as sampled dynamical systems or sparse subsets of integer domains.

License Information