Level sets of the Takagi function: local level sets

The Takagi function ??: [0,1] ?? [0, 1] is a continuous non-differentiable function constructed by Takagi in 1903. The level sets L(y)?=?{x : ??(x)?=?y} of the Takagi function ??(x) are studied by introducing a notion of local level set into which level sets are partitioned. Local level sets are simple to analyze, reducing questions to understanding the relation of level sets to local level sets, which is more complicated. It is known that for a ??generic?? full Lebesgue measure set of ordinates y, the level sets are finite sets. In contrast, here it is shown for a ??generic?? full Lebesgue measure set of abscissas x, the level set L(??(x)) is uncountable. An interesting singular monotone function is constructed associated to local level sets, and is used to show the expected number of local level sets at a random level y is exactly ${\frac{3}{2}}$ .     

Weak tangent and level sets of Takagi functions

In this paper, we study some properties of Takagi functions and their level sets. We show that for Takagi functions $$T_{a,b}$$ with parameters a, b such that ab is a root of a Littlewood polynomial, there exist large level sets. As a consequence, we show that for some parameters a, b, the Assouad dimension of graphs of $$T_{a,b}$$ is strictly larger than their upper box dimension. In particular, we can find weak tangents of those graphs with large Hausdorff dimension, larger than the upper box dimension of the graphs.     

Level sets of the Takagi function: Hausdorff dimension

The Takagi function τ(x) is a continuous non-differentiable function on the unit interval defined by Takagi in 1903. This paper studies level sets L(y) = {x : τ(x) = y} of the Takagi function and bounds their Minkowski dimensions and Hausdorff dimensions above by 0.668. There exist level sets with Minkowski dimension 1/2. The method of proof involves a multiscale analysis that relies upon the self-similarity of τ(x) up to affine shifts.     

Level sets of the Takagi function: Hausdorff dimension

The Takagi function τ(x) is a continuous non-differentiable function on the unit interval defined by Takagi in 1903. This paper studies level sets L(y) = {x : τ(x) = y} of the Takagi function and bounds their Minkowski dimensions and Hausdorff dimensions above by 0.668. There exist level sets with Minkowski dimension 1/2. The method of proof involves a multiscale analysis that relies upon the self-similarity of τ(x) up to affine shifts.     

On the cardinalities of finite topologies

Following the ideas of Sharp [2,3], we will give a partial answer to the question: “Let k be an integer, k ? 2. What is the smallest integer m for which there is a topology on m points with k open sets.” We state several results in the theory of finite topologies by introducing the idea of generating topologies. Using this concept, it is possible to derive existence theorems and get numerical results in an easy manner.     

Level sets of signed Takagi functions

This paper examines level sets of functions of the form $$ f(x)=\sum_{n=0}^\infty \frac{r_n}{2^n}\phi(2^n x), $$ where $\phi(x)=\operatorname{dist}\, (x,\mathbb {Z})$ , the distance from x to the nearest integer, and r _n =±1 for each n. Such functions are referred to as signed Takagi functions. The case when r _n =1 for all n is the classical Takagi function, a well-known example of a continuous but nowhere differentiable function. For f of the above form, the maximum and minimum values of f are expressed in terms of the sequence {r _n }. It is then shown that almost all level sets of f are finite (with respect to Lebesgue measure on the range of f), but the set of ordinates y with an uncountably large level set is residual in the range of f. The concept of a local level set of the Takagi function, due to Lagarias and Maddock, is extended to arbitrary signed Takagi functions. It is shown that the average number of local level sets contained in a level set of f is the reciprocal of the height of the graph of f, and consequently, this average lies between 3/2 and 2. These results generalize recent findings by Buczolich [8], Lagarias and Maddock [14], and Allaart [3].     

On the sum of cardinalities of extremum maximal independent sets

Upper bounds are established for the sum of the smallest and largest cardinalities of maximal independent sets in simple undirected graphs with p vertices and minimum degree k, for the cases k = 1, 2 and $\text{k ?}\text{1}\text{2}\text{p}$.     

Order statistics and estimating cardinalities of massive data sets

A new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data is introduced here. It is based on order statistics rather than on bit patterns in binary representations of numbers. Three families of estimators are analyzed. They attain a standard error of using M units of storage, which places them in the same class as the best known algorithms so far. The algorithms have a very simple internal loop, which gives them an advantage in terms of processing speed. For instance, a memory of only 12 kB and only few seconds are sufficient to process a multiset with several million elements and to build an estimate with accuracy of order 2 percent. The algorithms are validated both by mathematical analysis and by experimentations on real internet traffic.     

Possible cardinalities of irredundant bases for finite closure structures

We indicate certain connections between the rank and cardinality of a finite closure structure, and the relative sizes of its irredundant bases. A class of examples is described which shows that in general our theorem can not be strengthened.     

The Hausdorff dimension of the level sets of Takagi’s function

Recently, Maddock (2006) [12] has conjectured that the Hausdorff dimension of each level set of Takagi’s function is at most 1/2. We prove this conjecture using the self-affinity of the function of Takagi and the existing relationship between the Hausdorff and box-counting dimensions.     

On the Poincaré series and cardinalities of finite reflection groups

Let be a crystallographic reflection group with length function . We give a short and elementary derivation of the identity , where the product ranges over positive roots , and denotes the sum of the coordinates of with respect to the simple roots. We also prove that in the noncrystallographic case, this identity is valid in the limit ; i.e., .

     

Maximal antipodal sets of compact classical symmetric spaces and their cardinalities I

We classify and explicitly describe maximal antipodal sets of some compact classical symmetric spaces and those of their quotient spaces by making use of suitable embeddings of these symmetric spaces into compact classical Lie groups. We give the cardinalities of maximal antipodal sets and we determine the maximum of the cardinalities and maximal antipodal sets whose cardinalities attain the maximum.     

New characterizations of the Takagi function via functional equations

We provide two new characterizations of the Takagi function as the unique bounded solution of some systems of two functional equations. The results are independent of those obtained by Kairies (Wy? Szko? Ped Krakow Rocznik Nauk Dydakt Prace Mat 196:73–82, 1998), Kairies (Aequ Math 53:207–241, 1997), Kairies (Aequ Math 58:183–191, 1999) and Kairies et al. (Rad Mat 4:361–374, 1989; Errata, Rad Mat 5:179–180, 1989).     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

Recent hypertopologies and continuity of the value function and of the constrained level sets

Given a continuous function f: X→R, sufficient conditions are offered for the continuity of the value function v(A):=inf{f{x): x ε A} and of the level set multifunction Lev(A, α) := {x ε A: f(x)?α}, with respect to recently defined topologies on the closed sets of a metric space.     

Continuity properties of the normal cone to the level sets of a quasiconvex function

Two main properties of the subgradient mapping of convex functions are transposed for quasiconvex ones. The continuity of the functionxf(x)^–1f(x) on the domain where it is defined is deduced from some continuity properties of the normal coneN to the level sets of the quasiconvex functionf. We also prove that, under a pseudoconvexity-type condition, the normal coneN(x) to the set {x:f(x)f(x)} can be expressed as the convex hull of the limits of type {N(x _n)}, where {x _n} is a sequence converging tox and contained in a dense subsetD. In particular, whenf is pseudoconvex,D can be taken equal to the set of points wheref is differentiable.This research was completed while the second author was on a sabbatical leave at the University of Montreal and was supported by a NSERC grant. It has its origin in the doctoral thesis of the first author (Ref. 1), prepared under the direction of the second author.The authors are grateful to an anonymous referee and C. Zalinescu for their helpful remarks on a previous version of this paper.