text:
# Graph homomorphism

A homomorphism from the flower snark J5 into the cycle graph C5.
It is also a retraction onto the subgraph on the central five vertices. Thus J5 is in fact homomorphically equivalent to the core C5.

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.[1] The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs).[2] The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research.[3]

## Definitions

In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed. A graph homomorphism[4] f  from a graph G = (V(G), E(G)) to a graph H = (V(H), E(H)), written

f : GH

is a function from V(G) to V(H) that maps endpoints of each edge in G to endpoints of an edge in H. Formally, {u,v} ∈ E(G) implies {f(u),f(v)} ∈ E(H), for all pairs of vertices u, v in V(G). If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just:

GH .

The above definition is extended to directed graphs. Then, for a homomorphism f : GH, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G.

There is an injective homomorphism from G to H (i.e., one that never maps distinct vertices to one vertex) if and only if G is a subgraph of H. If a homomorphism f : GH is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism, then f is a graph isomorphism.[5]

Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology.[6] They are defined as surjective homomorphisms (i.e., something maps to each vertex) that are also locally bijective, that is, a bijection on the neighbourhood of each vertex. An example is the bipartite double cover, formed from a graph by splitting each vertex v into v0 and v1 and replacing each edge u,v with edges u0,v1 and v0,u1. The function mapping v0 and v1 in the cover to v in the original graph is a homomorphism and a covering map.

Graph homeomorphism is a different notion, not related directly to homomorphisms. Roughly speaking, it requires injectivity, but allows mapping edges to paths (not just to edges). Graph minors are a still more relaxed notion.

### Cores and retracts

K7, the complete graph with 7 vertices, is a core.

Two graphs G and H are homomorphically equivalent if GH and HG.[4] The maps are not necessarily surjective or nor injective. For instance, the complete bipartite graphs K2,2 and K3,3 are homomorphically equivalent: each map can be defined as taking the left (resp. right) half of the domain graph and mapping to just one vertex in the left (resp. right) half of the image graph.

A retraction is a homomorphism r from a graph G to a subgraph H of G such that r(v) = v for each vertex v of H. In this case the subgraph H is called a retract of G.[7]

A core is a graph with no homomorphism to any proper subgraph. Equivalently, a core can be defined as a graph that does not retract to any proper subgraph.[8] Every graph G is homomorphically equivalent to a unique core (up to isomorphism), called the core of G.[9] Notably, this is not true in general for infinite graphs.[10] However, the same definitions apply to directed graphs and a directed graph is also equivalent to a unique core. Every graph and every directed graph contains its core as a retract and as an induced subgraph.[7]

For example, all complete graphs Kn and all odd cycles (cycle graphs of odd length) are cores. Every 3-colorable graph G that contains a triangle (that is, has the complete graph K3 as a subgraph) is homomorphically equivalent to K3. This is because, on one hand, a 3-coloring of G is the same as a homomorphism GK3, as explained below. On the other hand, every subgraph of G trivially admits a homomorphism into G, implying K3G. This also means that K3 is the core of any such graph G. Similarly, every bipartite graph that has at least one edge is equivalent to K2.[11]

## Connection to colorings

A k-coloring, for some integer k, is an assignment of one of k colors to each vertex of a graph G such that the endpoints of each edge get different colors. The k-colorings of G correspond exactly to homomorphisms from G to the complete graph Kk.[12] Indeed, the vertices of Kk correspond to the k colors, and two colors are adjacent as vertices of Kk if and only if they are different. Hence a function defines a homomorphism to Kk if and only if it maps adjacent vertices of G to different colors (i.e., it is a k-coloring). In particular, G is k-colorable if and only if it is Kk-colorable.[12]

If there are two homomorphisms GH and HKk, then their composition GKk is also a homomorphism.[13] In other words, if a graph H can be colored with k colors, and there is a homomorphism from G to H, then G can also be k-colored. Therefore, GH implies χ(G) ≤ χ(H), where χ denotes the chromatic number of a graph (the least k for which it is k-colorable).[14]

### Variants

General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph H are the available colors and edges of H describe which colors are compatible, then an H-coloring of G is an assignment of colors to vertices of G such that adjacent vertices get compatible colors. Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs. Circular colorings can be defined using homomorphisms into circular complete graphs, refining the usual notion of colorings.[15] Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs.[16] T-colorings correspond to homomorphisms into certain infinite graphs.[17] An oriented coloring of a directed graph is a homomorphism into any oriented graph.[18] An L(2,1)-coloring is a homomorphism into the complement of the path graph that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex.[19]

### Orientations without long paths

Another interesting connection concerns orientations of graphs. An orientation of an undirected graph G is any directed graph obtained by choosing one of the two possible orientations for each edge. An example of an orientation of the complete graph Kk is the transitive tournament Tk with vertices 1,2,…,k and arcs from i to j whenever i < j. A homomorphism between orientations of graphs G and H yields a homomorphism between the undirected graphs G and H, simply by disregarding the orientations. On the other hand, given a homomorphism GH between undirected graphs, any orientation H of H can be pulled back to an orientation G of G so that G has a homomorphism to H. Therefore, a graph G is k-colorable (has a homomorphism to Kk) if and only if some orientation of G has a homomorphism to Tk.[20]

A folklore theorem states that for all k, a directed graph G has a homomorphism to Tk if and only if it admits no homomorphism from the directed path Pk+1.[21] Here Pn is the directed graph with vertices 1, 2, …, n and edges from i to i + 1, for i = 1, 2, …, n − 1. Therefore, a graph is k-colorable if and only if it has an orientation that admits no homomorphism from Pk+1. This statement can be strengthened slightly to say that a graph is k-colorable if and only if some orientation contains no directed path of length k (no Pk+1 as a subgraph). This is the Gallai–Hasse–Roy–Vitaver theorem.

## Connection to constraint satisfaction problems

### Examples

Graph H of non-consecutive weekdays, isomorphic to the complement graph of C7 and to the circular clique K7/2

Some scheduling problems can be modeled as a question about finding graph homomorphisms.[22][23] As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph G, with an edge between any two courses that are attended by some common student. The time slots form a graph H, with an edge between any two slots that are distant enough in time. For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then H would be the complement graph of C7. A graph homomorphism from G to H is then a schedule assigning courses to time slots, as specified.[22] To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from H.

A simple frequency allocation problem can be specified as follows: a number of transmitters in a wireless network must choose a frequency channel on which they will transmit data. To avoid interference, transmitters that are geographically close should use channels with frequencies that are far apart. If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism. It should go from the graph of transmitters G, with edges between pairs that are geographically close, to the graph of channels H, with edges between channels that are far apart. While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can added to the edges of G. Those that do not communicate at the same time can be removed from it. Similarly, channel pairs that are far apart but exhibit harmonic interference can be removed from the edge set of H.[24]

In each case, these simplified models display many of the issues that have to be handled in practice.[25] Constraint satisfaction problems, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.

### Formal view

Graphs and directed graphs can be viewed as a special case of the far more general notion called relational structures (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set).[26][3] Under this view, homomorphisms of such structures are exactly graph homomorphisms. In general, the question of finding a homomorphism from one relational structure to another is a constraint satisfaction problem (CSP). The case of graphs gives a concrete first step that helps to understand more complicated CSPs. Many algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs.[3]

For graphs G and H, the question of whether G has a homomorphism to H corresponds to a CSP instance with only one kind of constraint,[3] as follows. The variables are the vertices of G and the domain for each variable is the vertex set of H. An evaluation is a function that assigns to each variable an element of the domain, so a function f from V(G) to V(H). Each edge or arc (u,v) of G then corresponds to the constraint ((u,v), E(H)). This is a constraint expressing that the evaluation should map the arc (u,v) to a pair (f(u),f(v)) that is in the relation E(H), that is, to an arc of H. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from G to H.

## Structure of homomorphisms

Compositions of homomorphisms are homomorphisms.[13] In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a preorder on graphs.[27] Let the equivalence class of a graph G under homomorphic equivalence be [G]. The equivalence class can also be represented by the unique core in [G]. The relation → is a partial order on those equivalence classes; it defines a poset.[28]

Let G < H denote that there is a homomorphism from G to H, but no homomorphism from H to G. The relation → is a dense order, meaning that for all (undirected) graphs G, H such that G < H, there is a graph K such that G < K < H (this holds except for the trivial cases G = K0 or K1).[29][30] For example, between any two complete graphs (except K0, K1) there are infinitely many circular complete graphs, corresponding to rational numbers between natural numbers.[31]

The poset of equivalence classes of graphs under homomorphisms is a distributive lattice, with the join of [G] and [H] defined as (the equivalence class of) the disjoint union [GH], and the meet of [G] and [H] defined as the tensor product [G × H] (the choice of graphs G and H representing the equivalence classes [G] and [H] does not matter).[32] The join-irreducible elements of this lattice are exactly connected graphs. This can be shown using the fact that a homomorphism maps a connected graph into one connected component of the target graph.[33][34] The meet-irreducible elements of this lattice are exactly the multiplicative graphs. These are the graphs K such that a product G × H has a homomorphism to K only when one of G or H also does. Identifying multiplicative graphs lies at the heart of Hedetniemi's conjecture.[35][36]

Graph homomorphisms also form a category, with graphs as objects and homomorphisms as arrows.[37] The initial object is the empty graph, while the terminal object is the graph with one vertex and one loop at that vertex. The tensor product of graphs is the category-theoretic product and the exponential graph is the exponential object for this category.[36][38] Since these two operations are always defined, the category of graphs is a cartesian closed category. For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a Heyting algebra.[36][38]

For directed graphs the same definitions apply. In particular → is a partial order on equivalence classes of directed graphs. It is distinct from the order → on equivalence classes of undirected graphs, but contains it as a suborder. This is because every undirected graph can be thought of as a directed graph where every arc (u,v) appears together with its inverse arc (v,u), and this does not change the definition of homomorphism. The order → for directed graphs is again a distributive lattice and a Heyting algebra, with join and meet operations defined as before. However, it is not dense. There is also a category with directed graphs as objects and homomorphisms as arrows, which is again a cartesian closed category.[39][38]

### Incomparable graphs

The Grötzsch graph, incomparable to K3

There are many incomparable graphs with respect to the homomorphism preorder, that is, pairs of graphs such that neither admits a homomorphism into the other.[40] One way to construct them is to consider the odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism from the cycle graph on g vertices to G. For this reason, if GH, then the odd girth of G is greater than or equal to the odd girth of H.[41]

On the other hand, if GH, then the chromatic number of G is less than or equal to the chromatic number of H. Therefore, if G has strictly larger odd girth than H and strictly larger chromatic number than H, then G and H are incomparable.[40] For example, the Grötzsch graph is 4-chromatic and triangle-free (it has girth 4 and odd girth 5),[42] so it is incomparable to the triangle graph K3.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are Kneser graphs[43] and generalized Mycielskians.[44] A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an antichain in the homomorphism preorder).[45] Other properties, such as density of the homomorphism preorder, can be proved using such families.[46] Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see Girth and graph coloring).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs Cn, with vertices 1, 2, …, n and edges from i to i + 1 (for i = 1, 2, …, n − 1) and from n to 1. There is a homomorphism from Cn to Ck (n, k ≥ 3) if and only if n is a multiple of k. In particular, directed cycle graphs Cn with n prime are all incomparable.[47]

## Computational complexity

In the graph homomorphism problem, an instance is a pair of graphs (G,H) and a solution is a homomorphism from G to H. The general decision problem, asking whether there is any solution, is NP-complete.[48] However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve. Methods that apply when restraining the left side G are very different than for the right side H, but in each case a dichotomy (a sharp boundary between easy and hard cases) is known or conjectured.

### Homomorphisms to a fixed graph

The homomorphism problem with a fixed graph H on the right side of each instance is also called the H-coloring problem. When H is the complete graph Kk, this is the graph k-coloring problem, which is solvable in polynomial time for k = 0, 1, 2, and NP-complete otherwise.[49] In particular, K2-colorability of a graph G is equivalent to G being bipartite, which can be tested in linear time. More generally, whenever H is a bipartite graph, H-colorability is equivalent to K2-colorability (or K0 / K1-colorability when H is empty/edgeless), hence equally easy to decide.[50] Pavol Hell and Jaroslav Nešetřil proved that, for undirected graphs, no other case is tractable:

Hell–Nešetřil theorem (1990): The H-coloring problem is in P when H is bipartite and NP-complete otherwise.[51][52]

This is also known as the dichotomy theorem for (undirected) graph homomorphisms, since it divides H-coloring problems into NP-complete or P problems, with no intermediate cases. For directed graphs, the situation is more complicated and in fact equivalent to the much more general question of characterizing the complexity of constraint satisfaction problems.[53] It turns out that H-coloring problems for directed graphs are just as general and as diverse as CSPs with any other kinds of constraints.[54][55] Formally, a (finite) constraint language (or template) Γ is a finite domain and a finite set of relations over this domain. CSP(Γ) is the constraint satisfaction problem where instances are only allowed to use constraints in Γ.

Theorem (Feder, Vardi 1998): For every constraint language Γ, the problem CSP(Γ) is equivalent under polynomial-time reductions to some H-coloring problem, for some directed graph H.[55]

Intuitively, this means that every algorithmic technique or complexity result that applies to H-coloring problems for directed graphs H applies just as well to general CSPs. In particular, one can ask whether the Hell–Nešetřil theorem can be extended to directed graphs. By the above theorem, this is equivalent to the Feder–Vardi conjecture (aka CSP conjecture, dichotomy conjecture) on CSP dichotomy, which states that for every constraint language Γ, CSP(Γ) is NP-complete or in P.[48]. This conjecture was proved in 2017 independently by Dmitry Zhuk and Andrei Bulatov, leading the following corollary:

Corollary (Bulatov 2017; Zhuk 2017): The H-coloring problem on directed graphs, for a fixed H, is either in P or NP-complete.

### Homomorphisms from a fixed family of graphs

The homomorphism problem with a single fixed graph G on left side of input instances can be solved by brute-force in time |V(H)|O(|V(G)|), so polynomial in the size of the input graph H.[56] In other words, the problem is trivially in P for graphs G of bounded size. The interesting question is then what other properties of G, beside size, make polynomial algorithms possible.

The crucial property turns out to be treewidth, a measure of how tree-like the graph is. For a graph G of treewidth at most k and a graph H, the homomorphism problem can be solved in time |V(H)|O(k) with a standard dynamic programming approach. In fact, it is enough to assume that the core of G has treewidth at most k. This holds even if the core is not known.[57][58]

The exponent in the |V(H)|O(k)-time algorithm cannot be lowered significantly: no algorithm with running time |V(H)|o(tw(G) /log tw(G)) exists, assuming the exponential time hypothesis (ETH), even if the inputs are restricted to any class of graphs of unbounded treewidth.[59] The ETH is an unproven assumption similar to P ≠ NP, but stronger. Under the same assumption, there are also essentially no other properties that can be used to get polynomial time algorithms. This is formalized as follows:

Theorem (Grohe): For a computable class of graphs ${\displaystyle {\mathcal {G}}}$, the homomorphism problem for instances ${\displaystyle (G,H)}$ with ${\displaystyle G\in {\mathcal {G}}}$ is in P if and only if graphs in ${\displaystyle {\mathcal {G}}}$ have cores of bounded treewidth (assuming ETH).[58]

One can ask whether the problem is at least solvable in a time arbitrarily highly dependent on G, but with a fixed polynomial dependency on the size of H. The answer is again positive if we limit G to a class of graphs with cores of bounded treewidth, and negative for every other class.[58] In the language of parameterized complexity, this formally states that the homomorphism problem in ${\displaystyle {\mathcal {G}}}$ parameterized by the size (number of edges) of G exhibits a dichotomy. It is fixed-parameter tractable if graphs in ${\displaystyle {\mathcal {G}}}$ have cores of bounded treewidth, and W[1]-complete otherwise.

The same statements hold more generally for constraint satisfaction problems (or for relational structures, in other words). The only assumption needed is that constraints can involve only a bounded number of variables (all relations are of some bounded arity, 2 in the case of graphs). The relevant parameter is then the treewidth of the primal constraint graph.[59]

## Notes

1. ^ Hell & Nešetřil 2004, p. 27.
2. ^ Hell & Nešetřil 2004, p. 109.
3. ^ a b c d
4. ^ a b For introductions, see (in order of increasing length): Cameron (2006); Geňa & Tardif (1997); Hell & Nešetřil (2004).
5. ^ Geňa & Tardif 1997, Observation 2.3.
6. ^ Godsil & Royle 2001, p. 115.
7. ^ a b Hell & Nešetřil 2004, p. 19.
8. ^ Hell & Nešetřil 2004, Proposition 1.31.
9. ^ Cameron 2006, Proposition 2.3; Hell & Nešetřil 2004, Corollary 1.32.
10. ^ Hell & Nešetřil 2004, p. 34.
11. ^ Cameron 2006, p. 4, Proposition 2.5.
12. ^ a b Cameron 2006, p. 1; Hell & Nešetřil 2004, Proposition 1.7.
13. ^ a b Hell & Nešetřil 2004, §1.7.
14. ^ Hell & Nešetřil 2004, Corollary 1.8.
15. ^ Hell & Nešetřil 2004, §6.1; Geňa & Tardif 1997, §4.4.
16. ^ Hell & Nešetřil 2004, §6.2; Geňa & Tardif 1997, §4.5.
17. ^ Hell & Nešetřil 2004, §6.3.
18. ^ Hell & Nešetřil 2004, §6.4.
19. ^ Fiala, J.; Kratochvíl, J. (2002), "Partial covers of graphs", Discussiones Mathematicae Graph Theory, 22 (1): 89–99, doi:10.7151/dmgt.1159
20. ^ Hell & Nešetřil 2004, pp. 13–14.
21. ^ Hell & Nešetřil 2004, Proposition 1.20.
22. ^ a b Cameron 2006, p. 1.
23. ^ Hell & Nešetřil 2004, §1.8.
24. ^ Hell & Nešetřil 2004, pp. 30–31.
25. ^ Hell & Nešetřil 2004, pp. 31–32.
26. ^ Hell & Nešetřil 2004, p. 28, note relational structures are called relational systems there.
27. ^ Hell & Nešetřil 2004, §3.1.
28. ^ Hell & Nešetřil 2004, Theorem 3.1.
29. ^ Hell & Nešetřil 2004, Theorem 3.30; Geňa & Tardif 1997, Theorem 2.33.
30. ^ Welzl, E. (1982), "Color-families are dense", Theoret. Comput. Sci., 17: 29–41, doi:10.1016/0304-3975(82)90129-3
31. ^ Hell & Nešetřil 2004, p. 192; Geňa & Tardif 1997, p. 127.
32. ^ Hell & Nešetřil 2004, Proposition 3.2, distributivity is stated in Proposition 2.4; Geňa & Tardif 1997, Theorem 2.37.
33. ^ Kwuida, Léonard; Lehtonen, Erkko (2011), "On the Homomorphism Order of Labeled Posets", Order, Springer, 28 (2): 251–265, arXiv:0911.0200, doi:10.1007/s11083-010-9169-x
34. ^ Gray 2014, Lemma 3.7.
35. ^ Tardif, C. (2008), "Hedetniemi's conjecture, 40 years later" (PDF), Graph Theory Notes of New York, 54: 46–57, MR 2445666.
36. ^ a b c Dwight, D.; Sauer, N. (1996), "Lattices arising in categorial investigations of Hedetniemi's conjecture", Discrete Math., 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W
37. ^ Hell & Nešetřil 2004, p. 125.
38. ^ a b c
39. ^
40. ^ a b Hell & Nešetřil 2004, p. 7.
41. ^ Geňa & Tardif 1997, Observation 2.6.
42. ^
43. ^ Geňa & Tardif 1997, Proposition 3.14.
44. ^ Gyárfás, A.; Jensen, T.; Stiebitz, M. (2004), "On Graphs With Strongly Independent Color-Classes", J. Graph Theory, 46 (1): 1–14, doi:10.1002/jgt.10165
45. ^ Hell & Nešetřil 2004, Proposition 3.4.
46. ^ Hell & Nešetřil 2004, p. 96.
47. ^ Hell & Nešetřil 2004, p. 35.
48. ^ a b Bodirsky 2007, §1.3.
49. ^ Hell & Nešetřil 2004, §5.1.
50. ^ Hell & Nešetřil 2004, Proposition 5.1.
51. ^ Hell & Nešetřil 2004, §5.2.
52. ^ Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", JCTB, 48 (1): 92–110, doi:10.1016/0095-8956(90)90132-J
53. ^ Hell & Nešetřil 2004, §5.3.
54. ^ Hell & Nešetřil 2004, Theorem 5.14.
55. ^ a b
56. ^ Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A.; (2016). Tight bounds for graph homomorphism and subgraph isomorphism. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM. pp. 1643–1649. arXiv:1507.03738. Bibcode:2015arXiv150703738F. ISBN 978-1-611974-33-1.CS1 maint: extra punctuation (link) CS1 maint: uses authors parameter (link)
57. ^ Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. (2002). Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002). pp. 310–326. doi:10.1007/3-540-46135-3_21.
58. ^ a b c Grohe, Martin (2007), "The complexity of homomorphism and constraint satisfaction problems seen from the other side", J. ACM, 54 (1), doi:10.1145/1206035.1206036
59. ^ a b Marx, Dániel (2010), "Can You Beat Treewidth?", Theory of Computing, 6: 85–112, doi:10.4086/toc.2010.v006a005


text:
# Euclidean algorithm for $\gcd(60,17)$

Hay I am going over some old exams and hit this:

(a) Use the Euclidean algorithm to show that $\gcd(60; 17) = 1$.

(b) Hence find integers $x, y$ satisfying $60x + 17y = 1$.

(c) Find another solution in integers to $60x + 17y = 1$ (distinct from your previous answer).

Finding the gcd is easy but i can seem to find any help on the rest. Can someone point me at something that might help?

For (a), you should have seen that $$60=17\cdot 3+9\\17=9\cdot 1+8\\9=8\cdot 1+1,$$ whence \begin{align}1 &= 9-8\\ &= 9-(17-9)\\ &= 9\cdot 2-17\\ &= (60-17\cdot 3)\cdot 2-17\\ &= 60\cdot 2+17\cdot(-7).\end{align} For (c), you'll need to pick an $a$ and a $b$ such that $a,b\ne 0$ and $$1=60\cdot(1+a)+17\cdot(-7+b).$$ I leave it to you to find such $a,b$. It isn't too hard.
So it's important that you realize how these parts fit together. Let's do the first bit, i.e., go through the Euclidean algorithm: $$60 = 3(17)+9\\ 17=9+8\\ 9=8+1$$ Since we've reached a remainder of $1$, we can conclude that the gcd of the 2 numbers is, in fact, $1$. In order to solve the second part, we can now use our work, reversing our steps as follows: $$1=9-8\\ 1=9-(17-9)=2(9)-17\\ 1=2(60-3(17))-17=2(60)-7(17)$$ That is, we now have the solution $x=2,y=-7$. To get the other answers, add $17\mu$ to $x$ and subtract $60\mu$ from $y$ for some integer $\mu$.
This is the time to review the Extended Euclicean Algorithm. This algorithm uncovers $d = \gcd(a, b)$ as well as the $x, y$, in: $ax + by = d$.
You may choose among many ways to determine $x, y$; each method you find at the link above demonstrates the method with an example. First walk through the given examples, then apply to your question, going back and forth, as needed, to learn a method well.
But do learn one method/strategy, and learn the the method well; don't just let others' hand you an answer: you won't learn that way. You need to know a method well enough to use it and apply it when preparing for and taking an exam, e.g. And try testing your skills when the $\gcd(a, b) \neq 1$.

format: plain


text:
# Math Help - Not understanding answer...

The question posed is: "Suppose you flip a coin n times. If you win a dollar every time the coin comes up heads and lose a dollar every time it comes up tails, what is the probability that you will win k dollars?"

The answer given is: "If 2 doesn't divide $n + k$, the probability is 0. If 2 does divide $n + k$, the probability is ${n \choose \frac {n + k}{2} }$"

Does this make sense to anyone?

2. Originally Posted by earachefl
The question posed is: "Suppose you flip a coin n times. If you win a dollar every time the coin comes up heads and lose a dollar every time it comes up tails, what is the probability that you will win k dollars?"

The answer given is: "If 2 doesn't divide $n + k$, the probability is 0. If 2 does divide $n + k$, the probability is ${n \choose \frac {n + k}{2} }$"

Does this make sense to anyone?
To win k dollars requires n1 wins and n2 losses such that n1+n2=n, and
n1-n2=k.

This last imples that 2 n1 - (n1+n2) = k, so:

2 n1 = k+n

Hence k+n is even so the probabilty of winning k dollars in n trials is 0 if k+n is odd.

Also if k+n is even then the number of wins is (k+n)/2, and the probability of this is:

$
p(k, n) = {n \choose \frac{k+n}{2}} (1/2)^n
$

RonL

3. So they did leave out part of the answer:
$
(1/2)^n
$

which does make sense. Thanks!


text:
# zbMATH — the first resource for mathematics

Multivariate observations. (English) Zbl 0627.62052
Wiley Series in Probability and Mathematical Statistics. Probability and Mathematical Statistics. New York etc.: John Wiley & Sons. XX, 686 p. (TUB, Fachbibl. Stat.: 85 291) (1984).
The basic prerequisites for reading this book are a good knowledge of matrix algebra and an acquaintance with the multivariate normal distribution, multiple linear regression, and simple analysis of variance and covariance models. This book could be regarded as a companion volume to the author’s book ‘Linear regression analysis.’ (1977; Zbl 0354.62055).
Chapter 1 discusses the nature of multivariate data and problems of simultaneous inference. Chapter 2 selects from the extensive subject of multivariate distribution theory sufficient ideas to indicate the breadth of the subject and to provide a basis for later proofs. Attention is focused on the multivariate normal distribution, Wishart’s distribution, Hotelling’s $$T^ 2$$ distribution, together with the multivariate beta distribution and some of its derivatives. Inference for the multivariate normal, both in the one- and two-sample cases, is discussed extensively in Chapter 3, while Chapter 4 surveys graphical and data-oriented techniques. Chapter 5 discusses at length the many practical methods for expressing multivariate data in fewer dimensions in the hope of tracking down clustering or internal structure more effectively.
The growing field of discriminant analysis is reviewed in Chapter 6, while Chapter 7 endeavors to summarize the essentials of the almost unmanageable body of literature on cluster analysis. Chapters 8 and 9 develop linear models, with the general theory given in Chapter 8 and applications to simple multivariate analysis of variance and covariance models given in Chapter 9. The final chapter, Chapter 10, is mainly concerned with computational techniques; however, log-linear models and incomplete data are also discussed briefly.
Appendices A and B summarize a number of useful results in matrix algebra, with projection matrices discussed in Appendix B. Order statistics and probability plotting are considered in Appendix C, and Appendix D is a collection of useful statistical tables. Finally, there is a set of outline solutions for the exercises.

##### MSC:
 62Hxx Multivariate analysis 62-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to statistics 62-07 Data analysis (statistics) (MSC2010) 62J10 Analysis of variance and covariance (ANOVA)


text:
Least-squares Solution z of the Overdetermined System

ktcyper03

Find the Least-squares Solution z of the Overdetermined System
|-3 1 | | 70 |
| 1 1 | x = | 21 |
|-7 1 | | 110 |
| 5 1 | |-35 |

Excuse my poorly typed notation as that is supposed to be a matrix times x = another matrix.

TKHunny

If your 4x2 matrix is A, have you considered multiplying from the left with $$\displaystyle \left[\left(A^{T}\cdot A\right)^{-1}\cdot A^{T}\right]$$?

CaptainBlack


text:
21
Mar 21

A combination of several options in one trade is called a strategy. Here we discuss a strategy called a call debit spread. The word "debit" in this name means that a trader has to pay for it. The rule of thumb is that if it is a debit (you pay for a strategy), then it is less risky than if it is a credit (you are paid). Let $c(K)$ denote the call price with the strike $K,$ suppressing all other variables that influence the call price.

Assumption. The market values higher events of higher probability. This is true if investors are rational and the market correctly reconciles views of different investors.

We need the following property: if $K_{1} are two strike prices, then for the corresponding call prices (with the same expiration and underlying asset) one has $c(K_{1})>c(K_{2}).$

Proof.  A call price is higher if the probability of it being in the money at expiration is higher. Let $S(T)$ be the stock price at expiration $T.$ Since $T$ is a moment in the future, $S(T)$ is a random variable. For a given strike $K,$ the call is said to be in the money at expiration if $S(T)>K.$ If $K_{1} and $S(T)>K_{2},$ then $S(T)>K_{1}.$ It follows that the set $\{ S(T)>K_{2}\}$ is a subset of the set $\{S(T)>K_{1}\} .$ Hence the probability of the event $\{S(T)>K_{2}\}$ is lower than that of the event $\{S(T)>K_{1}\}$ and $c(K_{1})>c(K_{2}).$

Call debit spread strategy. Select two strikes $K_{1} buy $c(K_{1})$ (take a long position) and sell $c(K_{2})$ (take a short position). You pay $p=c(K_{1})-c(K_{2})>0$ for this.

Our purpose is to derive the payoff for this strategy. We remember that if $S(T)\leq K,$ then the call $c(K)$ expires worthless.

Case $S(T)\leq K_{1}.$ In this case both options expire worthless and the payoff is the initial outlay: payoff $=-p.$

Case $K_{1} Exercising the call $c(K_{1})$ and immediately selling the stock at the market price you gain $S(T)-K_{1}.$ The second option expires worthless. The payoff is: payoff $=S(T)-K_{1}-p.$ (In fact, you are assigned stock and selling it is up to you).

Case $K_{2} Both options are exercised. The gain from $c(K_{1})$ is, as above, $S(T)-K_{1}.$ The holder of the long call $c(K_{2})$ buys from you at price $K_{2}.$ Since your position is short, you have nothing to do but comply. You buy at $S(T)$ and sell at $K_{2}.$ Thus the loss from $-c(K_{2})$ is $K_{2}-S(T).$ The payoff is: payoff $=\left(S(T)-K_{1}\right) +\left( K_{2}-S(T)\right) -p=K_{2}-K_{1}-p.$

Summarizing, we get:

payoff $=\left\{\begin{array}{ll} -p, & S(T)\leq K_{1} \\ S(T)-K_{1}-p, & K_{1}

Normally, the strikes are chosen so that $K_{2}-K_{1}>p.$ From the payoff expression we see then that the maximum profit is $K_{2}-K_{1}-p>0,$ the maximum loss is $-p$ and the breakeven stock price is $S(T)=K_{1}+p.$ This is illustrated in Figure 1, where the stock price at expiration is on the horizontal axis.

Figure 1. Payoff for call debit strategy. Source: https://www.optionsbro.com/

Conclusion. For the strategy to be profitable, the price at expiration should satisfy $S(T)\geq K_{1}+p.$ Buying a call debit spread is appropriate when the price is expected to stay in that range.

In comparison with the long call position $c(K_{1}),$ taking at the same time the short call position $-c(K_{2})$ allows one to reduce the initial outlay. This is especially important when the stock volatility is high, resulting in a high call price. In the difference $c(K_{1})-c(K_{2})$ that volatility component partially cancels out.

Remark. There is an important issue of choosing the strikes. Let $S$ denote the stock price now. The payoff expression allows us to rank the next choices in the order of increasing risk: 1) $K_1 (both options are in the money, less risk), 2) $K_1 and 3) $K_1 (both options are out of the money, highest risk).  Also remember that a call debit spread is less expensive than buying $c(K_{1})$ and selling $c(K_{2})$ in two separate transactions.

Exercise. Analyze a call credit spread, in which you sell $c(K_{1})$ and buy $c(K_{2})$.


text:
Question

# Why is less effort needed to lift a load over an inclined plane as compared to lifting the load directly?

Solution

## For an inclined plain mechanical advantage =L/E, where L is the load and E is the effort. L/E =length of the inclined plain (l)/height (h) ; which is >1(since l>h) Therefore effort<load. hence less effort is  Required because mechanical advantage increases.

Suggest corrections


text:
RANDOM DYNAMICS

PHILOSOPHICAL INTRODUCTION

In the search for the most fundamental theory of physics one usually looks for a simplest possible model, and at present the most popular candidate on the market is superstrings theory (is superstring theory that simple?...).
But could it not be that the fundamental "World Machinery" (or theory) could be extremely complicated? We see that we have some very beautiful and simple laws of Nature such as Newton's laws, Hooke's law, The Standard Model and so on - how could such transparency and simplicity arise from a very complex fundamental "World Machinery"?
It is not totally unlikely that complicated models could lead to a very simple law. This is illustrated by imagining a rather complicated solid state theory (such as the theory of atoms with quantum mechanics or for that matter Rudger Boskovic's classical theory of atomic forces) leading to Hooke's law:

where is the length of a pulled stick, the force pulling it, and is the derivative.

Our Hooke's law derivation is only supposed to work in the limit where the force that pulls the solid object or stick is very small.
The Random Dynamics project is based on the idea that all known laws of Nature can, in a similar way as Hooke's law, be derived in some limit(s), practically independent of the underlying theory of the World Machinery.
The limit which could suggestively be the relevant limit for most laws, would be that the fundamental energy scale is very big compared to the energies of the elementary particles even in very high energy experiments. A likely fundamental energy scale would be the Planck energy, 1.2 Gev.

To get an idea of why this Random Dynamics project, if successful, should be superior to every other scheme, such as string theories or alike, you can read about the motivation, and to get an idea of how a sub-project of Random Dynamics looks at its best, we advice you to look for the derivation of Lorentz invariance and why we have 4+1 dimensions.
To derive this, some physical laws (such as an abstract form of Quantum Mechanics and a very general version of Quantum Field Theory) - but of course not Lorentz invariance - have to be assumed. Really we assume that at the end of the Random Dynamics, we shall have a long series of derivations starting from almost nothing (we often refer to this "almost nothing" as the complicated mathematical structure ). The development of all the steps in this chain of derivation, hopefully ending in the Standard Model (including all the laws from different branches of physics), is not completed. A listing of the chain as we imagine it at present, is however found here. One may still be worried if the project is at all possible without somehow sneaking in information on the way. We of course hope to avoid putting in extra information, there is however one kind of information that we are allowed to sneak in - because we have to do so. That is the information concerning how we interpret different elements in the random model with the various physical concepts. Also in e.g. the Standard Model, you need this interpretation scheme, because you have to put in the assumption as to which of the phenomenologically found interactions are to be identified with gauge group in the group U(1) x SU(2) x SU(3).


text:
## Journal of Mathematical Imaging and Vision

 Short Title: J. Math. Imaging Vis. Publisher: Springer US, New York, NY ISSN: 0924-9907; 1573-7683/e Online: http://link.springer.com/journal/volumesAndIssues/10851 Comments: Indexed cover-to-cover
 Documents Indexed: 1,291 Publications (since 1992) References Indexed: 1,078 Publications with 41,848 References.
all top 5

### Latest Issues

 64, No. 5 (2022) 64, No. 4 (2022) 64, No. 3 (2022) 64, No. 2 (2022) 64, No. 1 (2022) 63, No. 9 (2021) 63, No. 8 (2021) 63, No. 7 (2021) 63, No. 6 (2021) 63, No. 5 (2021) 63, No. 4 (2021) 63, No. 3 (2021) 63, No. 2 (2021) 63, No. 1 (2021) 62, No. 9 (2020) 62, No. 8 (2020) 62, No. 6-7 (2020) 62, No. 5 (2020) 62, No. 4 (2020) 62, No. 3 (2020) 62, No. 2 (2020) 62, No. 1 (2020) 61, No. 9 (2019) 61, No. 8 (2019) 61, No. 7 (2019) 61, No. 6 (2019) 61, No. 5 (2019) 61, No. 4 (2019) 61, No. 3 (2019) 61, No. 2 (2019) 61, No. 1 (2019) 60, No. 9 (2018) 60, No. 8 (2018) 60, No. 7 (2018) 60, No. 6 (2018) 60, No. 5 (2018) 60, No. 4 (2018) 60, No. 3 (2018) 60, No. 2 (2018) 60, No. 1 (2018) 59, No. 3 (2017) 59, No. 2 (2017) 59, No. 1 (2017) 58, No. 3 (2017) 58, No. 2 (2017) 58, No. 1 (2017) 57, No. 3 (2017) 57, No. 2 (2017) 57, No. 1 (2017) 56, No. 3 (2016) 56, No. 2 (2016) 56, No. 1 (2016) 55, No. 3 (2016) 55, No. 2 (2016) 55, No. 1 (2016) 54, No. 3 (2016) 54, No. 2 (2016) 54, No. 1 (2016) 53, No. 3 (2015) 53, No. 2 (2015) 53, No. 1 (2015) 52, No. 3 (2015) 52, No. 2 (2015) 52, No. 1 (2015) 51, No. 3 (2015) 51, No. 2 (2015) 51, No. 1 (2015) 50, No. 3 (2014) 50, No. 1-2 (2014) 49, No. 3 (2014) 49, No. 2 (2014) 49, No. 1 (2014) 48, No. 3 (2014) 48, No. 2 (2014) 48, No. 1 (2014) 47, No. 3 (2013) 47, No. 1-2 (2013) 46, No. 3 (2013) 46, No. 2 (2013) 46, No. 1 (2013) 45, No. 3 (2013) 45, No. 2 (2013) 45, No. 1 (2013) 44, No. 3 (2012) 44, No. 2 (2012) 44, No. 1 (2012) 43, No. 3 (2012) 43, No. 2 (2012) 43, No. 1 (2012) 42, No. 2-3 (2012) 42, No. 1 (2012) 41, No. 3 (2011) 41, No. 1-2 (2011) 40, No. 3 (2011) 40, No. 2 (2011) 40, No. 1 (2011) 39, No. 3 (2011) 39, No. 2 (2011) 39, No. 1 (2011) 38, No. 3 (2010) ...and 91 more Volumes
all top 5

### Authors

 17 Schnörr, Christoph 15 Dougherty, Edward R. 14 Najman, Laurent 13 Steidl, Gabriele 12 Florack, Luc M. J. 12 Pock, Thomas 12 Weickert, Joachim 11 Aujol, Jean-François 11 Bertrand, Gilles 11 Couprie, Michel 11 Duits, Remco 11 Morel, Jean-Michel 11 Nielsen, Mads 10 Bayro-Corrochano, Eduardo 10 Hintermüller, Michael 10 Lindeberg, Tony 10 ter Haar Romeny, Bart M. 9 Cohen, Laurent D. 9 Kimmel, Ron 9 Lauze, François 9 Nikolova, Mila 9 Ronse, Christian 8 Boxer, Laurence 8 Chambolle, Antonin 8 Kuijper, Arjan 8 Lachaud, Jacques-Olivier 8 Passat, Nicolas 7 Aubert, Gilles 7 Barrera, Junior 7 Cousty, Jean 7 Kahl, Fredrik 7 Mazo, Loïc 7 Scherzer, Otmar 7 Viergever, Max A. 7 Welk, Martin 6 Bartoli, Adrien 6 Bruckstein, Alfred Marcel 6 Burger, Martin 6 Caselles Costa, Vicent 6 Ciesielski, Krzysztof Chris 6 Citti, Giovanna 6 Coeurjolly, David 6 Delon, Julie 6 Desolneux, Agnès 6 Durou, Jean-Denis 6 Heijmans, Henk J. A. M. 6 Kenmochi, Yukiko 6 Pesquet, Jean-Christophe 6 Petrou, Maria 6 Pinoli, Jean-Charles 6 Quéau, Yvain 6 Sarti, Alessandro 6 Sochen, Nir 6 Sommer, Gerald 6 Tai, Xuecheng 6 Talbot, Hugues 6 Vese, Luminita A. 6 Žunić, Joviša D. 5 Almansa, Andrés 5 Åström, Kalle 5 Bhowmick, Partha 5 Boutry, Nicolas 5 Breuß, Michael 5 Chojnacki, Wojciech 5 Debayle, Johan 5 Deledalle, Charles-Alban 5 Géraud, Thierry 5 Gilboa, Guy 5 Grigoryan, Artyom M. 5 Morigi, Serena 5 Peyré, Gabriel 5 Rieck, Michael Q. 5 Schönlieb, Carola-Bibiane 5 Soatto, Stefano 5 Sur, Frédéric 5 Wang, Xiangyang 4 Astola, Jaakko T. 4 Batard, Thomas 4 Bekkers, Erik J. 4 Bertozzi, Andrea Louise 4 Bouthemy, Patrick 4 Brooks, Michael J. 4 Ceko, Matthew 4 Chan, Tony Fan-Cheong 4 Cremers, Daniel 4 Darbon, Jerome 4 Elmoataz, Abderrahim 4 Fadili, Jalal M. 4 Gousseau, Yann 4 Graña, Manuel 4 Groisser, David 4 Ladjal, Saïd 4 Lanza, Alessandro 4 Lellmann, Jan 4 Lorenz, Dirk Alfred 4 Miranda, Paulo André Vechiatto 4 Mirebeau, Jean-Marie 4 Moisan, Lionel 4 Olsson, Carl-Olof 4 Oskarsson, Magnus ...and 2,116 more Authors
all top 5

### Fields

 954 Computer science (68-XX) 664 Information and communication theory, circuits (94-XX) 158 Numerical analysis (65-XX) 95 Statistics (62-XX) 90 Biology and other natural sciences (92-XX) 63 Calculus of variations and optimal control; optimization (49-XX) 62 Operations research, mathematical programming (90-XX) 43 Partial differential equations (35-XX) 38 Differential geometry (53-XX) 33 Harmonic analysis on Euclidean spaces (42-XX) 21 Linear and multilinear algebra; matrix theory (15-XX) 17 Geometry (51-XX) 17 Convex and discrete geometry (52-XX) 16 General and overarching topics; collections (00-XX) 16 Global analysis, analysis on manifolds (58-XX) 15 Probability theory and stochastic processes (60-XX) 15 Systems theory; control (93-XX) 14 Combinatorics (05-XX) 12 Algebraic topology (55-XX) 10 Order, lattices, ordered algebraic structures (06-XX) 10 Manifolds and cell complexes (57-XX) 8 Algebraic geometry (14-XX) 8 Integral transforms, operational calculus (44-XX) 7 Measure and integration (28-XX) 7 Dynamical systems and ergodic theory (37-XX) 7 General topology (54-XX) 6 Abstract harmonic analysis (43-XX) 5 Number theory (11-XX) 5 Approximations and expansions (41-XX) 5 Operator theory (47-XX) 5 Fluid mechanics (76-XX) 4 Group theory and generalizations (20-XX) 4 Topological groups, Lie groups (22-XX) 4 Functional analysis (46-XX) 4 Optics, electromagnetic theory (78-XX) 3 Mathematical logic and foundations (03-XX) 3 Functions of a complex variable (30-XX) 3 Several complex variables and analytic spaces (32-XX) 3 Special functions (33-XX) 3 Ordinary differential equations (34-XX) 3 Integral equations (45-XX) 3 Statistical mechanics, structure of matter (82-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 History and biography (01-XX) 2 Commutative algebra (13-XX) 2 Nonassociative rings and algebras (17-XX) 2 Difference and functional equations (39-XX) 2 Astronomy and astrophysics (85-XX) 2 Geophysics (86-XX) 1 Field theory and polynomials (12-XX) 1 Real functions (26-XX) 1 Mechanics of particles and systems (70-XX)

### Citations contained in zbMATH Open

786 Publications have been cited 5,892 times in 3,916 Documents Cited by Year
A first-order primal-dual algorithm for convex problems with applications to imaging. Zbl 1255.68217
Chambolle, Antonin; Pock, Thomas
2011
An algorithm for total variation minimization and applications. Zbl 1366.94048
Chambolle, Antonin
2004
An inertial forward-backward algorithm for monotone inclusions. Zbl 1327.47063
Lorenz, Dirk A.; Pock, Thomas
2015
A fast spectral method for active 3D shape reconstruction. Zbl 1366.94056
Li, Jia; Hero, Alfred O.
2004
A variational approach to remove outliers and impulse noise. Zbl 1366.94065
Nikolova, Mila
2004
A classical construction for the digital fundamental group. Zbl 0946.68151
Boxer, Laurence
1999
A combined first and second order variational approach for image reconstruction. Zbl 1362.94009
Papafitsoros, K.; Schönlieb, C. B.
2014
Removing multiplicative noise by Douglas-Rachford splitting methods. Zbl 1287.94016
Steidl, G.; Teuber, T.
2010
Image decomposition into a bounded variation component and an oscillating component. Zbl 1371.94031
Aujol, Jean-François; Aubert, Gilles; Blanc-Féraud, Laure; Chambolle, Antonin
2005
Overview of the geometries of shape spaces and diffeomorphism groups. Zbl 1310.58005
Bauer, Martin; Bruveris, Martins; Michor, Peter W.
2014
Curvature based image registration. Zbl 1034.68110
Fischer, Bernd; Modersitzki, Jan
2003
Automated regularization parameter selection in multi-scale total variation models for image restoration. Zbl 1255.68230
Dong, Yiqiu; Hintermüller, Michael; Rincon-Camacho, M. Monserrat
2011
iPiasco: inertial proximal algorithm for strongly convex optimization. Zbl 1327.90219
Ochs, Peter; Brox, Thomas; Pock, Thomas
2015
Properties of digital homotopy. Zbl 1383.68090
Boxer, Laurence
2005
Grey-scale morphology based on fuzzy logic. Zbl 0994.68168
Deng, Ting-Quan; Heijmans, Henk J. A. M.
2002
Variational optic flow computation with a spatio-temporal smoothness constraint. Zbl 0988.68821
Weickert, Joachim; Schnörr, Christoph
2001
A variational model to remove the multiplicative noise in ultrasound images. Zbl 1255.68240
Jin, Zhengmeng; Yang, Xiaoping
2011
Some first-order algorithms for total variation based image restoration. Zbl 1287.94012
Aujol, Jean-François
2009
Generalized Gaussian scale-space axiomatics comprising linear scale-space, affine scale-space and spatio-temporal scale-space. Zbl 1255.68250
Lindeberg, Tony
2011
A sparse multiscale algorithm for dense optimal transport. Zbl 1351.49037
Schmitzer, Bernhard
2016
Intrinsic statistics on Riemannian manifolds: Basic tools for geometric measurements. Zbl 1478.94072
Pennec, Xavier
2006
Relations between regularization and diffusion filtering. Zbl 0945.68183
Scherzer, Otmar; Weickert, Joachim
2000
The Riemannian geometry of the space of positive-definite matrices and its application to the regularization of positive-definite matrix-valued data. Zbl 1255.68195
2011
On advances in statistical modeling of natural images. Zbl 1033.68133
Srivastava, A.; Lee, A. B.; Simoncelli, E. P.; Zhu, S.-C.
2003
Adaptive fractional-order multi-scale method for image denoising. Zbl 1255.68278
Zhang, Jun; Wei, Zhihui; Xiao, Liang
2012
The two-dimensional Clifford-Fourier transform. Zbl 1122.42016
Brackx, Fred; De Schepper, Nele; Sommen, Frank
2006
Linear scale-space has first been proposed in Japan. Zbl 1002.68177
Weickert, Joachim; Ishikawa, Seiji; Imiya, Atsushi
1999
Matrix recipes for hard thresholding methods. Zbl 1311.90141
Kyrillidis, Anastasios; Cevher, Volkan
2014
Deep neural networks motivated by partial differential equations. Zbl 1434.68522
2020
Edge detection by Helmholtz principle. Zbl 0988.68819
Desolneux, Agnès; Moisan, Lionel; Morel, Jean-Michel
2001
Sliced and Radon Wasserstein barycenters of measures. Zbl 1332.94014
Bonneel, Nicolas; Rabin, Julien; Peyré, Gabriel; Pfister, Hanspeter
2015
Bilevel parameter learning for higher-order total variation regularisation models. Zbl 1425.94010
De los Reyes, J. C.; Schönlieb, C.-B.; Valkonen, T.
2017
Image denoising and decomposition with total variation minimization and oscillatory functions. Zbl 1366.94072
Vese, Luminita A.; Osher, Stanley J.
2004
Multiplicative calculus in biomedical image analysis. Zbl 1255.92014
Florack, Luc; Van Assen, Hans
2012
Preconditioned Douglas-Rachford algorithms for TV- and TGV-regularized variational imaging problems. Zbl 1343.94003
Bredies, Kristian; Sun, Hong Peng
2015
Regularizing flows for constrained matrix-valued images. Zbl 1366.94049
Chefd’hotel, C.; Tschumperlé, D.; Deriche, R.; Faugeras, O.
2004
Image restoration with discrete constrained total variation. I: Fast and exact optimization. Zbl 1478.94026
Darbon, Jérôme; Sigelle, Marc
2006
Intrinsic polynomials for regression on Riemannian manifolds. Zbl 1310.53038
Hinkle, Jacob; Fletcher, P. Thomas; Joshi, Sarang
2014
Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization. Zbl 1302.65142
2014
Preserving topology by a digitization process. Zbl 0895.68138
Latecki, Longin Jan; Conrad, Christopher; Gross, Ari
1998
A cortical based model of perceptual completion in the roto-translation space. Zbl 1478.92100
Citti, G.; Sarti, A.
2006
Association fields via cuspless sub-Riemannian geodesics in SE(2). Zbl 1296.49040
Duits, R.; Boscain, U.; Rossi, F.; Sachkov, Y.
2014
Nonnegative diffusion orientation distribution function. Zbl 1276.94004
Qi, Liqun; Yu, Gaohang; Xu, Yi
2013
Optimal algorithm for shape from shading and path planning. Zbl 0995.68101
Kimmel, Ron; Sethian, James A.
2001
Interval-valued and intuitionistic fuzzy mathematical morphologies as special cases of $$\mathbb{L}$$-fuzzy mathematical morphology. Zbl 1255.68267
Sussner, Peter; Nachtegael, Mike; Mélange, Tom; Deschrijver, Glad; Esmi, Estevão; Kerre, Etienne
2012
Connectivity on complete lattices. Zbl 0914.06002
Serra, Jean
1998
Total cyclic variation and generalizations. Zbl 1298.94011
Cremers, Daniel; Strekalovskiy, Evgeny
2013
On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration. Zbl 1255.68210
Bonettini, Silvia; Ruggiero, Valeria
2012
Poisson noise reduction with non-local PCA. Zbl 1365.94050
Salmon, Joseph; Harmany, Zachary; Deledalle, Charles-Alban; Willett, Rebecca
2014
Analysis of inpainting via clustered sparsity and microlocal analysis. Zbl 1362.94007
King, Emily J.; Kutyniok, Gitta; Zhuang, Xiaosheng
2014
Convolution products for hypercomplex Fourier transforms. Zbl 1292.42007
Bujack, Roxana; De Bie, Hendrik; De Schepper, Nele; Scheuermann, Gerik
2014
Some topological properties of surfaces in $$Z^3$$. Zbl 0942.68132
Bertrand, Gilles; Malgouyres, Rémy
1999
An inexact Newton-CG-type active contour approach for the minimization of the Mumford-Shah functional. Zbl 1366.65066
Hintermüller, Michael; Ring, Wolfgang
2004
Two enhanced fourth order diffusion models for image denoising. Zbl 1255.68235
Guidotti, Patrick; Longo, Kate
2011
Convex image denoising via non-convex regularization with parameter selection. Zbl 1391.94088
Lanza, Alessandro; Morigi, Serena; Sgallari, Fiorella
2016
A partial splitting augmented Lagrangian method for low patch-rank image decomposition. Zbl 1332.68270
Han, Deren; Kong, Weiwei; Zhang, Wenxing
2015
Optimal selection of the regularization function in a weighted total variation model. II: Algorithm, its analysis and numerical tests. Zbl 1382.94016
Hintermüller, Michael; Rautenberg, Carlos N.; Wu, Tao; Langer, Andreas
2017
A multi-orientation analysis approach to retinal vessel tracking. Zbl 1291.92075
Bekkers, Erik; Duits, Remco; Berendschot, Tos; ter Haar Romeny, Bart
2014
Landmark matching via large deformation diffeomorphisms on the sphere. Zbl 1366.94052
Glaunès, Joan; Vaillant, Marc; Miller, Michael I.
2004
Segmentation with depth but without detecting junctions. Zbl 1033.68132
Esedoglu, Selim; March, Riccardo
2003
Image and video colorization using vector-valued reproducing kernel Hilbert spaces. Zbl 1392.94042
Quang, Minh Ha; Kang, Sung Ha; Le, Triet M.
2010
Image matching using generalized scale-space interest points. Zbl 1357.94023
Lindeberg, Tony
2015
Constrained and SNR-based solutions for TV-Hilbert space image denoising. Zbl 1287.94010
Aujol, Jean-François; Gilboa, Guy
2006
Optimal selection of the regularization function in a weighted total variation model. I: Modelling and theory. Zbl 1382.94015
Hintermüller, Michael; Rautenberg, Carlos N.
2017
Morphological and linear scale spaces for fiber enhancement in DW-MRI. Zbl 1303.92049
Duits, Remco; Haije, Tom Dela; Creusen, Eric; Ghosh, Arpan
2013
Retinex by higher order total variation $$L^1$$ decomposition. Zbl 1400.94025
Liang, Jingwei; Zhang, Xiaoqun
2015
Dimensional properties of graphs and digital spaces. Zbl 1191.05088
Evako, Alexander V.; Kopperman, Ralph; Mukhin, Yurii V.
1996
Image sharpening by flows based on triple well potentials. Zbl 1366.94051
Gilboa, Guy; Sochen, Nir; Zeevi, Yehoshua Y.
2004
Geodesic shooting for computational anatomy. Zbl 1478.92084
Miller, Michael I.; Trouvé, Alain; Younes, Laurent
2006
Sparse non-negative stencils for anisotropic diffusion. Zbl 1365.68451
Fehrenbach, Jérôme; Mirebeau, Jean-Marie
2014
Multigrid convergence of calculated features in image analysis. Zbl 0969.68167
Klette, Reinhard; Žunić, Joviša
2000
Motor algebra of 3D kinematics: The case of the hand-eye calibration. Zbl 0969.68645
Bayro-Corrochano, Eduardo; Daniilidis, Kostas; Sommer, Gerald
2000
Tube methods for BV regularization. Zbl 1101.68927
Hinterberger, Walter; Hintermüller, Michael; Kunisch, Karl; von Oehsen, Markus; Scherzer, Otmar
2003
A theoretical tour of connectivity in image processing and analysis. Zbl 1040.68130
Braga-Neto, Ulisses; Goutsias, John
2003
Image sequence interpolation using optimal control. Zbl 1255.68220
Chen, Kanglin; Lorenz, Dirk A.
2011
Color image analysis by quaternion-type moments. Zbl 1331.68266
Chen, Beijing; Shu, Huazhong; Coatrieux, Gouenou; Chen, Gang; Sun, Xingming; Coatrieux, Jean Louis
2015
Image labeling by assignment. Zbl 1460.62101
Åström, Freddie; Petra, Stefania; Schmitzer, Bernhard; Schnörr, Christoph
2017
Properties of Gauss digitized shapes and digital surface integration. Zbl 1338.65060
Lachaud, Jacques-Olivier; Thibert, Boris
2016
A variational framework for region-based segmentation incorporating physical noise models. Zbl 1291.68402
Sawatzky, Alex; Tenbrinck, Daniel; Jiang, Xiaoyi; Burger, Martin
2013
Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis. Zbl 1398.65135
Duits, R.; Meesters, S. P. L.; Mirebeau, J.-M.; Portegies, J. M.
2018
Variational restoration and edge detection for color images. Zbl 1020.68079
Brook, Alexander; Kimmel, Ron; Sochen, Nir A.
2003
Inf-semilattice approach to self-dual morphology. Zbl 1020.68093
Heijmans, Henk J. A. M.; Keshet, Renato
2002
Proximal algorithms for multicomponent image recovery problems. Zbl 1255.68213
Briceño-Arias, L. M.; Combettes, P. L.; Pesquet, J.-C.; Pustelnik, N.
2011
A second-order TV-type approach for inpainting and denoising higher dimensional combined cyclic and vector space data. Zbl 1338.65155
Bergmann, Ronny; Weinmann, Andreas
2016
Homotopy equivalence in finite digital images. Zbl 1343.68270
Haarmann, Jason; Murphy, Meg P.; Peters, Casey S.; Staecker, P. Christopher
2015
Discrete total variation with finite elements and applications to imaging. Zbl 1448.94016
Herrmann, Marc; Herzog, Roland; Schmidt, Stephan; Vidal-Núñez, José; Wachsmuth, Gerd
2019
A Cahn-Hilliard system with a fidelity term for color image inpainting. Zbl 1381.94014
Cherfils, Laurence; Fakih, Hussein; Miranville, Alain
2016
Discretization in Hausdorff space. Zbl 0952.68150
Ronse, Christian; Tajine, Mohamed
2000
Digitally continuous multivalued functions, morphological operations and thinning algorithms. Zbl 1255.68231
Escribano, Carmen; Giraldo, Antonio; Sastre, María Asunción
2012
Nonlinear spectral analysis via one-homogeneous functionals: overview and future prospects. Zbl 1409.94182
Gilboa, Guy; Moeller, Michael; Burger, Martin
2016
Convex relaxation of a class of vertex penalizing functionals. Zbl 1293.49063
Bredies, Kristian; Pock, Thomas; Wirth, Benedikt
2013
Multi-class transductive learning based on $$\ell^1$$ relaxations of Cheeger cut and Mumford-Shah-Potts model. Zbl 1366.68230
Bresson, Xavier; Tai, Xue-Cheng; Chan, Tony F.; Szlam, Arthur
2014
Defect detection from multi-frequency limited data via topological sensitivity. Zbl 1337.76056
Funes, José Félix; Perales, José Manuel; Rapún, María-Luisa; Vega, José Manuel
2016
Rationalising the renormalisation method of Kanatani. Zbl 0990.68175
Chojnacki, Wojciech; Brooks, Michael J.; van den Hengel, Anton
2001
Diffusions and confusions in signal and image processing. Zbl 0994.94011
Sochen, N.; Kimmel, R.; Bruckstein, A. M.
2001
Soft morphological filtering. Zbl 0939.68911
Kuosmanen, Pauli; Astola, Jaakko
1995
Local discriminant bases and their applications. Zbl 0863.94004
Saito, Naoki; Coifman, Ronald R.
1995
The monogenic scale-space: a unifying approach to phase-based image processing in scale-space. Zbl 1478.94037
Felsberg, M.; Sommer, G.
2004
On using functions to describe the shape. Zbl 1020.68081
Kindratenko, Volodymyr V.
2003
Non-local methods with shape-adaptive patches (NLM-SAP). Zbl 1255.68227
Deledalle, Charles-Alban; Duval, Vincent; Salmon, Joseph
2012
Scale-covariant and scale-invariant Gaussian derivative networks. Zbl 07510341
Lindeberg, Tony
2022
Hough transform for detecting space curves in digital 3D models. Zbl 07510344
Romanengo, Chiara; Biasotti, Silvia; Falcidieno, Bianca
2022
Bilevel parameter learning for nonlocal image denoising models. Zbl 07363971
D’Elia, M.; De Los Reyes, J. C.; Miniguano-Trujillo, A.
2021
Image reconstruction by minimizing curvatures on image surface. Zbl 07358825
Zhong, Qiuxiang; Yin, Ke; Duan, Yuping
2021
Learning adaptive regularization for image labeling using geometric assignment. Zbl 07358835
Hühnerbein, Ruben; Savarino, Fabrizio; Petra, Stefania; Schnörr, Christoph
2021
Cortical-inspired Wilson-Cowan-type equations for orientation-dependent contrast perception modelling. Zbl 07358838
Bertalmío, Marcelo; Calatroni, Luca; Franceschi, Valentina; Franceschiello, Benedetta; Prandi, Dario
2021
From Riemannian trichromacy to quantum color opponency via hyperbolicity. Zbl 07363967
Berthier, Michel; Provenzi, Edoardo
2021
Radon cumulative distribution transform subspace modeling for image classification. Zbl 07433020
Shifat-E-Rabbi, Mohammad; Yin, Xuwang; Rubaiyat, Abu Hasnat Mohammad; Li, Shiying; Kolouri, Soheil; Aldroubi, Akram; Nichols, Jonathan M.; Rohde, Gustavo K.
2021
An elastica-driven digital curve evolution model for image segmentation. Zbl 07358823
Antunes, Daniel; Lachaud, Jacques-Olivier; Talbot, Hugues
2021
PDE evolutions for M-smoothers in one, two, and three dimensions. Zbl 07358834
Welk, Martin; Weickert, Joachim
2021
Image morphing in deep feature spaces: theory and applications. Zbl 07358840
Effland, Alexander; Kobler, Erich; Pock, Thomas; Rajković, Marko; Rumpf, Martin
2021
Boundary ghosts for discrete tomography. Zbl 1490.68273
Ceko, Matthew; Petersen, Timothy; Svalbe, Imants; Tijdeman, Rob
2021
A quotient space formulation for generative statistical analysis of graphical data. Zbl 07363970
Guo, Xiaoyang; Srivastava, Anuj; Sarkar, Sudeep
2021
On inversion-free mapping and distortion minimization. Zbl 07432757
Naitsat, Alexander; Naitzat, Gregory; Zeevi, Yehoshua Y.
2021
Elastic shape analysis of planar objects using tensor field representations. Zbl 07433021
Zhang, Ruiyi; Srivastava, Anuj
2021
Deep neural networks motivated by partial differential equations. Zbl 1434.68522
2020
Variational networks: an optimal control approach to early stopping variational methods for image restoration. Zbl 1434.68626
Effland, Alexander; Kobler, Erich; Kunisch, Karl; Pock, Thomas
2020
Regularization by architecture: a deep prior approach for inverse problems. Zbl 1434.68505
Dittmer, Sören; Kluth, Tobias; Maass, Peter; Otero Baguer, Daniel
2020
Crouzeix-Raviart approximation of the total variation on simplicial meshes. Zbl 1486.49062
Chambolle, Antonin; Pock, Thomas
2020
A characterization of proximity operators. Zbl 07255773
Gribonval, Rémi; Nikolova, Mila
2020
A two-stage method for spectral-spatial classification of hyperspectral images. Zbl 1483.68282
Chan, Raymond H.; Kan, Kelvin K.; Nikolova, Mila; Plemmons, Robert J.
2020
Accelerated variational PDEs for efficient solution of regularized inversion problems. Zbl 1440.65124
Benyamin, Minas; Calder, Jeff; Sundaramoorthi, Ganesh; Yezzi, Anthony
2020
Forward stability of ResNet and its variants. Zbl 1434.68528
Zhang, Linan; Schaeffer, Hayden
2020
Provably scale-covariant continuous hierarchical networks based on scale-normalized differential expressions coupled in cascade. Zbl 1435.68291
Lindeberg, Tony
2020
Sparse reconstruction of log-conductivity in current density impedance tomography. Zbl 1437.35704
Gupta, Madhu; Mishra, Rohit Kumar; Roy, Souvik
2020
Networks for nonlinear diffusion problems in imaging. Zbl 1434.68496
Arridge, S.; Hauptmann, A.
2020
Geodesic analysis in Kendall’s shape space with epidemiological applications. Zbl 1437.53012
Nava-Yazdani, Esfandiar; Hege, Hans-Christian; Sullivan, T. J.; von Tycowicz, Christoph
2020
Efficiently testing digital convexity and recognizing digital convex polygons. Zbl 1482.68249
Crombez, Loïc; da Fonseca, Guilherme D.; Gerard, Yan
2020
Unsupervised assignment flow: label learning on feature manifolds by spatially regularized geometric assignment. Zbl 1483.68453
Zern, Artjom; Zisler, Matthias; Petra, Stefania; Schnörr, Christoph
2020
Residual networks as flows of diffeomorphisms. Zbl 1434.68521
Rousseau, François; Drumetz, Lucas; Fablet, Ronan
2020
A convex variational model for learning convolutional image atoms from incomplete data. Zbl 1434.68625
Chambolle, A.; Holler, M.; Pock, T.
2020
Shape analysis of surfaces using general elastic metrics. Zbl 07289203
Su, Zhe; Bauer, Martin; Preston, Stephen C.; Laga, Hamid; Klassen, Eric
2020
New type of Gegenbauer-Hermite monogenic polynomials and associated Clifford wavelets. Zbl 1455.94005
Arfaoui, Sabrine; Ben Mabrouk, Anouar; Cattani, Carlo
2020
Learning stable nonlinear cross-diffusion models for image restoration. Zbl 1439.65025
Barbeiro, Sílvia; Lobo, Diogo
2020
Adversarial noise attacks of deep learning architectures: stability analysis via sparse-modeled signals. Zbl 1434.68520
2020
Nonlocal elastica model for sparse reconstruction. Zbl 1455.94040
Yan, Mengyuan; Duan, Yuping
2020
New set of non-separable orthogonal invariant moments for image recognition. Zbl 1434.68540
Hjouji, Amal; EL-Mekkaoui, Jaouad; Jourhmane, Mostafa; Bouikhalene, Belaid
2020
Optimum cuts in graphs by general fuzzy connectedness with local band constraints. Zbl 1482.68261
de Moraes Braz, Caio; Miranda, Paulo A. V.; Ciesielski, Krzysztof Chris; Cappabianco, Fábio A. M.
2020
Local turn-boundedness: a curvature control for continuous curves with application to digitization. Zbl 1482.68254
Le Quentrec, Étienne; Mazo, Loïc; Baudrier, Étienne; Tajine, Mohamed
2020
Two polynomial time graph labeling algorithms optimizing max-norm-based objective functions. Zbl 1482.68180
Malmberg, Filip; Ciesielski, Krzysztof Chris
2020
New insights on the optimality conditions of the $$\ell_2-\ell_0$$ minimization problem. Zbl 1486.90158
Soubies, Emmanuel; Blanc-Féraud, Laure; Aubert, Gilles
2020
Tensor factorization with total variation and Tikhonov regularization for low-rank tensor completion in imaging data. Zbl 1486.90157
Lin, Xue-Lei; Ng, Michael K.; Zhao, Xi-Le
2020
A proximal interior point algorithm with applications to image processing. Zbl 1486.90209
Chouzenoux, Emilie; Corbineau, Marie-Caroline; Pesquet, Jean-Christophe
2020
Single image blind deblurring based on salient edge-structures and elastic-net regularization. Zbl 07289200
Yu, XiaoYuan; Xie, Wei
2020
2D geometric moment invariants from the point of view of the classical invariant theory. Zbl 07289201
Bedratyuk, Leonid
2020
On the generalized essential matrix correction: an efficient solution to the problem and its applications. Zbl 07289204
Miraldo, Pedro; Cardoso, João R.
2020
Variational models for color image correction inspired by visual perception and neuroscience. Zbl 07289208
Batard, Thomas; Hertrich, Johannes; Steidl, Gabriele
2020
Geometric interpretation of the multi-solution phenomenon in the P3P problem. Zbl 07289210
Wang, Bo; Hu, Hao; Zhang, Caixia
2020
Non-blind and blind deconvolution under Poisson noise using fractional-order total variation. Zbl 07289212
Chowdhury, Mujibur Rahman; Qin, Jing; Lou, Yifei
2020
Discrete total variation with finite elements and applications to imaging. Zbl 1448.94016
Herrmann, Marc; Herzog, Roland; Schmidt, Stephan; Vidal-Núñez, José; Wachsmuth, Gerd
2019
A convex geodesic selective model for image segmentation. Zbl 1448.94031
Roberts, Michael; Chen, Ke; Irion, Klaus L.
2019
An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration. Zbl 1487.94034
Zeng, Chao; Jia, Rui; Wu, Chunlin
2019
Data fitting on manifolds with composite Bézier-like curves and blended cubic splines. Zbl 07073924
Gousenbourger, Pierre-Yves; Massart, Estelle; Absil, P.-A.
2019
Chan-Vese reformulation for selective image segmentation. Zbl 1468.68275
Roberts, Michael; Spencer, Jack
2019
Geometric preservation of 2D digital objects under rigid motions. Zbl 1431.52023
Ngo, Phuc; Passat, Nicolas; Kenmochi, Yukiko; Debled-Rennesson, Isabelle
2019
Multiplicative noise removal based on the smooth diffusion equation. Zbl 1446.94013
Shan, Xiujie; Sun, Jiebao; Guo, Zhichang
2019
Reconstruction algorithms for photoacoustic tomography in heterogeneous damping media. Zbl 1455.94020
Haltmeier, Markus; Nguyen, Linh V.
2019
Fast algorithm of 3D discrete image orthogonal moments computation based on 3D cuboid. Zbl 1443.68202
Jahid, Tarik; Karmouni, Hicham; Sayyouri, Mhamed; Hmimid, Abdeslam; Qjidaa, Hassan
2019
Currents and finite elements as tools for shape space. Zbl 1468.65018
Benn, James; Marsland, Stephen; McLachlan, Robert I.; Modin, Klas; Verdier, Olivier
2019
RNLp: mixing nonlocal and TV-Lp methods to remove impulse noise from images. Zbl 1448.94009
Delon, Julie; Desolneux, Agnès; Sutour, Camille; Viano, Agathe
2019
A discrete framework to find the optimal matching between manifold-valued curves. Zbl 1485.58013
Le Brigant, Alice
2019
Unified models for second-order TV-type regularisation in imaging: a new perspective based on vector operators. Zbl 07073919
Brinkmann, Eva-Maria; Burger, Martin; Grah, Joana Sarah
2019
Repairing 3D binary images using the FCC grid. Zbl 1482.68242
Čomić, Lidija; Magillo, Paola
2019
Soft color morphology: a fuzzy approach for multivariate images. Zbl 1430.94009
Bibiloni, Pedro; González-Hidalgo, Manuel; Massanet, Sebastia
2019
Multi-scale arithmetization of linear transformations. Zbl 1444.03189
Mazo, Loïc
2019
A new hybrid form of Krawtchouk and Tchebichef polynomials: design and application. Zbl 1443.33029
Abdulhussain, Sadiq H.; Ramli, Abd Rahman; Mahmmod, Basheera M.; Saripan, M. Iqbal; Al-Haddad, S. A. R.; Jassim, Wissam A.
2019
Pointwise Besov space smoothing of images. Zbl 1454.94011
Buzzard, Gregery T.; Chambolle, Antonin; Cohen, Jonathan D.; Levine, Stacey E.; Lucier, Bradley J.
2019
Denoising of image gradients and total generalized variation denoising. Zbl 1487.94023
Komander, Birgit; Lorenz, Dirk A.; Vestweber, Lena
2019
Fractal descriptors of texture images based on the triangular prism dimension. Zbl 1445.68197
Florindo, João Batista; Bruno, Odemir Martinez
2019
Discrepancy: local/global shape characterization with a roundness bias. Zbl 1487.94021
Genctav, Asli; Tari, Sibel
2019
Acyclic partial matchings for multidimensional persistence: algorithm and combinatorial interpretation. Zbl 1431.55007
Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo
2019
A $$Q$$-convexity vector descriptor for image analysis. Zbl 1430.94006
Balázs, P.; Brunetti, S.
2019
Combinatorics of the Gauss digitization under translation in 2D. Zbl 1431.52021
Baudrier, Étienne; Mazo, Loïc
2019
Equiareal shape-from-template. Zbl 07073921
Casillas-Perez, David; Pizarro, Daniel; Fuentes-Jimenez, David; Mazo, Manuel; Bartoli, Adrien
2019
Inertial alternating generalized forward-backward splitting for image colorization. Zbl 07073925
Tan, Pauline; Pierre, Fabien; Nikolova, Mila
2019
Image anomalies: a review and synthesis of detection methods. Zbl 07073927
Ehret, Thibaud; Davy, Axel; Morel, Jean-Michel; Delbracio, Mauricio
2019
Some theoretical links between shortest path filters and minimum spanning tree filters. Zbl 1446.68160
Danda, Sravan; Challa, Aditya; Sagar, B. S. Daya; Najman, Laurent
2019
Component-graph construction. Zbl 1446.68182
Passat, Nicolas; Naegel, Benoît; Kurtz, Camille
2019
Regularization with metric double integrals of functions with values in a set of vectors. Zbl 1451.49038
Ciak, René; Melching, Melanie; Scherzer, Otmar
2019
How to make $$n$$-D plain maps defined on discrete surfaces Alexandrov-well-composed in a self-dual way. Zbl 1446.68176
Boutry, Nicolas; Géraud, Thierry; Najman, Laurent
2019
Factoring a homography to analyze projective distortion. Zbl 1446.51007
Crannell, Annalisa; Frantz, Marc; Futamura, Fumiko
2019
Robust model selection in 2D parametric motion estimation. Zbl 1446.68158
Bouthemy, Patrick; Toledo Acosta, Bertha Mayela; Delyon, Bernard
2019
Representation of surfaces with normal cycles and application to surface registration. Zbl 1468.68270
Roussillon, Pierre; Glaunès, Joan Alexis
2019
On visual periodicity estimation using singular value decomposition. Zbl 1468.68253
Kamel, Nidal; Kajo, Ibrahim; Ruichek, Yassine
2019
On the taut string interpretation and other properties of the Rudin-Osher-Fatemi model in one dimension. Zbl 1479.94071
Overgaard, Niels Chr
2019
A novel total generalized variation model for image dehazing. Zbl 1479.49071
Gu, Yanan; Yang, Xiaoping; Gao, Yiming
2019
Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis. Zbl 1398.65135
Duits, R.; Meesters, S. P. L.; Mirebeau, J.-M.; Portegies, J. M.
2018
A tutorial on well-composedness. Zbl 1435.68337
Boutry, Nicolas; Géraud, Thierry; Najman, Laurent
2018
Priors with coupled first and second order differences for manifold-valued image processing. Zbl 1436.49040
Bergmann, Ronny; Fitschen, Jan Henrik; Persch, Johannes; Steidl, Gabriele
2018
A novel diffeomorphic model for image registration and its algorithm. Zbl 1435.94052
Zhang, Daoping; Chen, Ke
2018
Path-value functions for which Dijkstra’s algorithm returns optimal mapping. Zbl 1397.05187
Ciesielski, Krzysztof Chris; Falcão, Alexandre Xavier; Miranda, Paulo A. V.
2018
Nonlocal myriad filters for Cauchy noise removal. Zbl 1435.94030
Laus, Friederike; Pierre, Fabien; Steidl, Gabriele
2018
Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps. Zbl 1420.94010
Cousty, Jean; Najman, Laurent; Kenmochi, Yukiko; Guimarães, Silvio
2018
Iterative regularization via dual diagonal descent. Zbl 1425.94013
Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia
2018
Highly corrupted image inpainting through hypoelliptic diffusion. Zbl 1406.94004
Boscain, Ugo V.; Chertovskih, Roman; Gauthier, Jean-Paul; Prandi, Dario; Remizov, Alexey
2018
Topology-preserving image segmentation by Beltrami representation of shapes. Zbl 1437.94011
Chan, Hei-Long; Yan, Shi; Lui, Lok-Ming; Tai, Xue-Cheng
2018
Fast-marching methods for curvature penalized shortest paths. Zbl 1435.65041
Mirebeau, Jean-Marie
2018
Design and processing of invertible orientation scores of 3D images. Zbl 1433.94012
Janssen, M. H. J.; Janssen, A. J. E. M.; Bekkers, E. J.; Bescós, J. Oliván; Duits, R.
2018
Whiteness constraints in a unified variational framework for image restoration. Zbl 1433.94014
Lanza, Alessandro; Morigi, Serena; Sciacchitano, Federica; Sgallari, Fiorella
2018
Spatio-temporal scale selection in video data. Zbl 1420.94015
Lindeberg, Tony
2018
...and 686 more Documents
all top 5

### Cited by 5,648 Authors

 44 Steidl, Gabriele 35 Tai, Xuecheng 33 Han, Sang-Eon 33 Schönlieb, Carola-Bibiane 31 Huang, Ting-Zhu 30 Zeng, Tie Yong 28 Chen, Ke 27 Osher, Stanley Joel 25 Duits, Remco 25 Weickert, Joachim 24 Boxer, Laurence 24 Chambolle, Antonin 23 Burger, Martin 23 Schnörr, Christoph 22 Scherzer, Otmar 21 Najman, Laurent 21 Ng, Michael Kwok-Po 21 Peyré, Gabriel 21 Shehu, Yekini 20 Pock, Thomas 20 Shen, Lixin 19 Boţ, Radu Ioan 19 Lv, Xiaoguang 19 Valkonen, Tuomo 18 Bloch, Isabelle 18 Citti, Giovanna 18 Han, Deren 18 Passat, Nicolas 17 Aujol, Jean-François 17 Hintermüller, Michael 17 Lachaud, Jacques-Olivier 17 Zhao, Xile 16 Bauer, Martin 16 Bredies, Kristian 16 Chan, Raymond Hon-Fu 16 Ronse, Christian 16 Wu, Chunlin 16 Yuan, Xiaoming 15 Cremers, Daniel 15 Dong, Qiaoli 15 Dong, Yiqiu 15 Duan, Yuping 15 Jung, Miyoun 15 Laghrib, Amine 15 Lindeberg, Tony 15 Pang, Zhifeng 15 Sarti, Alessandro 15 Weinmann, Andreas 14 Bruveris, Martins 14 Guo, Zhichang 14 Kang, Myungjoo 14 Li, Wuchen 14 Mazo, Loïc 14 Wu, Boying 14 Zhang, Xiaoqun 13 Cai, Xingju 13 Caselles Costa, Vicent 13 Csetnek, Ernö Robert 13 Desolneux, Agnès 13 Gilboa, Guy 13 Karaca, Ismet 13 Kenmochi, Yukiko 13 Li, Fang 13 Mirebeau, Jean-Marie 13 Tran Dinh Quoc 12 Breuß, Michael 12 Chan, Tony Fan-Cheong 12 Feng, Xiangchu 12 Lellmann, Jan 12 Lou, Yifei 12 Lu, Jian 12 Morel, Jean-Michel 12 Nikolova, Mila 12 Papadakis, Nicolas 12 Qi, Liqun 12 Storath, Martin 12 Trouvé, Alain 12 Welk, Martin 11 Bertrand, Gilles 11 Cousty, Jean 11 Lui, Lok Ming 11 Pennec, Xavier 11 Rumpf, Martin 11 Talbot, Hugues 11 Xu, Yuesheng 10 Bertozzi, Andrea Louise 10 Bonettini, Silvia 10 Boutry, Nicolas 10 Chernov, Nikolai Ivanovich 10 Couprie, Michel 10 Elmoataz, Abderrahim 10 Kang, Myeongmin 10 Lanza, Alessandro 10 Lee, Chang-Ock 10 Liu, Jun 10 Morigi, Serena 10 Munk, Axel 10 Quéau, Yvain 10 Shen, Zuowei 10 Sussner, Peter ...and 5,548 more Authors
all top 5

### Cited in 491 Journals

 557 Journal of Mathematical Imaging and Vision 215 SIAM Journal on Imaging Sciences 128 International Journal of Computer Vision 112 Journal of Scientific Computing 93 Inverse Problems 77 Inverse Problems and Imaging 71 Pattern Recognition 60 Applied Mathematics and Computation 60 SIAM Journal on Optimization 53 Computers & Mathematics with Applications 53 Journal of Computational and Applied Mathematics 50 Computational Optimization and Applications 49 Applied and Computational Harmonic Analysis 48 Information Sciences 48 Mathematical Problems in Engineering 45 SIAM Journal on Scientific Computing 43 Journal of Optimization Theory and Applications 35 Numerical Algorithms 34 International Journal of Computer Mathematics 31 Multidimensional Systems and Signal Processing 31 Advances in Applied Clifford Algebras 29 Advances in Computational Mathematics 28 Journal of Computational Physics 26 Mathematical Programming. Series A. Series B 26 Computational and Applied Mathematics 25 Applied Mathematical Modelling 23 Numerische Mathematik 22 Linear Algebra and its Applications 22 Journal of Inequalities and Applications 21 Optimization 20 Applied Numerical Mathematics 19 International Journal of Wavelets, Multiresolution and Information Processing 19 Electronic Journal of Statistics 18 Journal of Mathematical Analysis and Applications 17 Mathematical Methods in the Applied Sciences 17 The Annals of Statistics 17 Applied Mathematics and Optimization 17 SIAM Journal on Mathematics of Data Science 16 Discrete Applied Mathematics 16 Mathematics of Computation 16 Foundations of Computational Mathematics 15 Theoretical Computer Science 15 Optimization Methods & Software 14 Acta Applicandae Mathematicae 14 Neural Computation 14 Journal of Machine Learning Research (JMLR) 14 Optimization Letters 14 Set-Valued and Variational Analysis 13 Journal of Multivariate Analysis 13 SIAM Journal on Numerical Analysis 13 Inverse Problems in Science and Engineering 13 Applied General Topology 13 Journal of the Operations Research Society of China 13 Mathematical Morphology. Theory and Applications 12 Journal of the Franklin Institute 12 Fuzzy Sets and Systems 12 Journal of Inverse and Ill-Posed Problems 12 Abstract and Applied Analysis 11 Journal of Global Optimization 11 Computational Statistics and Data Analysis 10 Computer Methods in Applied Mechanics and Engineering 10 Numerical Functional Analysis and Optimization 10 Discrete & Computational Geometry 10 Journal of Nonlinear Science 10 Nonlinear Analysis. Real World Applications 10 Computational & Mathematical Methods in Medicine 10 Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A: Matemáticas. RACSAM 9 Automatica 9 Quarterly of Applied Mathematics 9 Circuits, Systems, and Signal Processing 9 International Journal of Approximate Reasoning 9 SIAM Journal on Mathematical Analysis 9 The Journal of Fourier Analysis and Applications 9 Analysis and Applications (Singapore) 9 Journal of Industrial and Management Optimization 9 European Series in Applied and Industrial Mathematics (ESAIM): Mathematical Modelling and Numerical Analysis 9 The Annals of Applied Statistics 8 Calcolo 8 Mathematical and Computer Modelling 8 SIAM Journal on Matrix Analysis and Applications 8 European Journal of Applied Mathematics 8 Calculus of Variations and Partial Differential Equations 8 ETNA. Electronic Transactions on Numerical Analysis 8 European Series in Applied and Industrial Mathematics (ESAIM): Control, Optimization and Calculus of Variations 8 Optimization and Engineering 8 Fixed Point Theory and Applications 8 Journal of Fixed Point Theory and Applications 8 East Asian Journal on Applied Mathematics 7 Computing 7 SIAM Journal on Applied Mathematics 7 Multiscale Modeling & Simulation 7 Journal of Computational and Graphical Statistics 7 Journal of Mathematics 6 Applicable Analysis 6 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods 6 Topology and its Applications 6 Neural Networks 6 Differential Geometry and its Applications 6 M$$^3$$AS. Mathematical Models & Methods in Applied Sciences 6 Journal of Statistical Computation and Simulation ...and 391 more Journals
all top 5

### Cited in 62 Fields

 1,510 Computer science (68-XX) 1,377 Information and communication theory, circuits (94-XX) 1,366 Numerical analysis (65-XX) 733 Operations research, mathematical programming (90-XX) 596 Calculus of variations and optimal control; optimization (49-XX) 434 Statistics (62-XX) 365 Partial differential equations (35-XX) 277 Biology and other natural sciences (92-XX) 259 Operator theory (47-XX) 171 Differential geometry (53-XX) 125 Linear and multilinear algebra; matrix theory (15-XX) 125 Harmonic analysis on Euclidean spaces (42-XX) 119 Probability theory and stochastic processes (60-XX) 98 Global analysis, analysis on manifolds (58-XX) 75 General topology (54-XX) 61 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 61 Systems theory; control (93-XX) 60 Algebraic topology (55-XX) 53 Combinatorics (05-XX) 53 Convex and discrete geometry (52-XX) 51 Mechanics of deformable solids (74-XX) 46 Real functions (26-XX) 44 Fluid mechanics (76-XX) 43 Functional analysis (46-XX) 37 Ordinary differential equations (34-XX) 35 Dynamical systems and ergodic theory (37-XX) 33 Integral transforms, operational calculus (44-XX) 33 Optics, electromagnetic theory (78-XX) 30 Order, lattices, ordered algebraic structures (06-XX) 30 Functions of a complex variable (30-XX) 27 Approximations and expansions (41-XX) 27 Manifolds and cell complexes (57-XX) 26 Geometry (51-XX) 25 Mathematical logic and foundations (03-XX) 25 Mechanics of particles and systems (70-XX) 21 Topological groups, Lie groups (22-XX) 20 Measure and integration (28-XX) 20 Statistical mechanics, structure of matter (82-XX) 16 Algebraic geometry (14-XX) 16 Geophysics (86-XX) 14 Integral equations (45-XX) 12 General and overarching topics; collections (00-XX) 12 Special functions (33-XX) 12 Quantum theory (81-XX) 9 Number theory (11-XX) 9 Abstract harmonic analysis (43-XX) 8 Classical thermodynamics, heat transfer (80-XX) 7 Commutative algebra (13-XX) 6 Nonassociative rings and algebras (17-XX) 6 Several complex variables and analytic spaces (32-XX) 6 Difference and functional equations (39-XX) 5 Associative rings and algebras (16-XX) 5 Group theory and generalizations (20-XX) 4 Field theory and polynomials (12-XX) 3 History and biography (01-XX) 3 Relativity and gravitational theory (83-XX) 3 Mathematics education (97-XX) 2 Potential theory (31-XX) 2 Astronomy and astrophysics (85-XX) 1 Category theory; homological algebra (18-XX) 1 $$K$$-theory (19-XX) 1 Sequences, series, summability (40-XX)


text:
Asymptotic bifurcation and second order elliptic equations on ${ℝ}^{N}$
Annales de l'I.H.P. Analyse non linéaire, Tome 32 (2015) no. 6, pp. 1259-1281.

This paper deals with asymptotic bifurcation, first in the abstract setting of an equation $G\left(u\right)=\lambda u$, where G acts between real Hilbert spaces and $\lambda \in ℝ$, and then for square-integrable solutions of a second order non-linear elliptic equation on ${ℝ}^{N}$. The novel feature of this work is that G is not required to be asymptotically linear in the usual sense since this condition is not appropriate for the application to the elliptic problem. Instead, G is only required to be Hadamard asymptotically linear and we give conditions ensuring that there is asymptotic bifurcation at eigenvalues of odd multiplicity of the H-asymptotic derivative which are sufficiently far from the essential spectrum. The latter restriction is justified since we also show that for some elliptic equations there is no asymptotic bifurcation at a simple eigenvalue of the H-asymptotic derivative if it is too close to the essential spectrum.

DOI : https://doi.org/10.1016/j.anihpc.2014.09.003
Classification : 35J91,  47J15
Mots clés : Asymptotic linearity, Asymptotic bifurcation, Nonlinear elliptic equation
@article{AIHPC_2015__32_6_1259_0,
author = {Stuart, C.A.},
title = {Asymptotic bifurcation and second order elliptic equations on ${\mathbb{R}}^{N}$
},
journal = {Annales de l'I.H.P. Analyse non lin\'eaire},
pages = {1259--1281},
publisher = {Elsevier},
volume = {32},
number = {6},
year = {2015},
doi = {10.1016/j.anihpc.2014.09.003},
zbl = {1330.35187},
mrnumber = {3425262},
language = {en},
url = {www.numdam.org/item/AIHPC_2015__32_6_1259_0/}
}
Stuart, C.A. Asymptotic bifurcation and second order elliptic equations on ${\mathbb{R}}^{N}$
. Annales de l'I.H.P. Analyse non linéaire, Tome 32 (2015) no. 6, pp. 1259-1281. doi : 10.1016/j.anihpc.2014.09.003. http://www.numdam.org/item/AIHPC_2015__32_6_1259_0/

[1] A. Ambrosetti, D. Arcoya, An Introduction to Nonlinear Functional Analysis and Elliptic Problems, Birkhäuser, Basel (2011) | MR 2816471 | Zbl 1228.46001

[2] E.N. Dancer, On bifurcation from infinity, Q. J. Math. 25 no. 2 (1974), 81 -84 | MR 346613 | Zbl 0282.47021

[3] K. Deimling, Nonlinear Functional Analysis, Springer-Verlag, Berlin (1985) | MR 787404 | Zbl 0559.47040

[4] J.-P. Dias, J. Hernandez, A remark on a paper by J.F. Toland and some applications to unilateral problems, Proc. R. Soc. Edinb. 75 (1976), 179 -182 | MR 442772 | Zbl 0358.47038

[5] A.L. Dontchev, R.T. Rockafellar, Implicit Functions and Solution Mappings, Springer, Heidelberg (2009) | MR 2515104 | Zbl 1172.49013

[6] A. Edelson, C.A. Stuart, The principal branch of solutions of a nonlinear elliptic eigenvalue problem on ${ℝ}^{N}$ , J. Differ. Equ. 124 (1996), 279 -301 | MR 1370142 | Zbl 0842.35029

[7] G. Evéquoz, C.A. Stuart, Hadamard differentiability and bifurcation, Proc. R. Soc. Edinb. A 137 (2007), 1249 -1285 | MR 2376879 | Zbl 1134.35014

[8] G. Evéquoz, C.A. Stuart, On differentiability and bifurcation, Adv. Math. Econ. 8 (2006), 155 -184 | MR 2766725 | Zbl 1107.47048

[9] T.M. Flett, Differential Analysis, Cambridge University Press, Cambridge (1980) | MR 561908 | Zbl 0442.34002

[10] F. Genoud, Bifurcation from infinity for an asymptotically linear problem on the half-line, Nonlinear Anal. 74 (2011), 4533 -4543 | MR 2810748 | Zbl 1229.34057

[11] F. Genoud, Global bifurcation for asymptotically linear Schrödinger equations, Nonlinear Differ. Equ. Appl. 20 (2013), 23 -35 | MR 3011311 | Zbl 1263.35110

[12] H. Koch, D. Tataru, Carleman estimates and absence of embedded eigenvalues, Commun. Math. Phys. 267 (2006), 419 -449 | MR 2252331 | Zbl 1151.35025

[13] M.A. Krasnoselskii, Topological Methods in the Theory of Nonlinear Integral Equations, Pergamon Press, Oxford (1964)

[14] M.A. Krasnoselskii, Positive Solutions of Operator Equations, Noordhoff, Groningen (1964)

[15] P.H. Rabinowitz, On bifurcation from infinity, J. Differ. Equ. 14 (1973), 462 -475 | MR 328705 | Zbl 0272.35017

[16] C.A. Stuart, An introduction to elliptic equation on ${ℝ}^{N}$ , A. Ambrosetti, K.-C. Chang, I. Ekeland (ed.), Nonlinear Functional Analysis and Applications to Differential Equations, World Scientific, Singapore (1998)

[17] C.A. Stuart, Bifurcation for some non-Fréchet differentiable problems, Nonlinear Anal. 69 (2008), 1011 -1024 | MR 2428773 | Zbl 1157.47045

[18] C.A. Stuart, Bifurcation and decay of solutions for a class of elliptic equations on ${ℝ}^{N}$ , Contemp. Math. vol. 540 (2011), 203 -230 | MR 2807416 | Zbl 1236.35010

[19] C.A. Stuart, Asymptotic linearity and Hadamard differentiability, Nonlinear Anal. 75 (2012), 4699 -4710 | MR 2927129 | Zbl 1269.46027

[20] C.A. Stuart, Bifurcation at isolated singular points of the Hadamard derivative, Proc. R. Soc. Edinb. (2014) | MR 3265543 | Zbl 1322.47060

[21] C.A. Stuart, Bifurcation at isolated eigenvalues for some elliptic equations on ${ℝ}^{N}$, preprint, 2012. | MR 3330744

[22] C.A. Stuart, H.-S. Zhou, Global branch of solutions for non-linear Schrödinger equations with deepening potential well, Proc. Lond. Math. Soc. (3) 92 (2006), 655 -681 | MR 2223540 | Zbl 1225.35091

[23] J.F. Toland, Asymptotic nonlinearity and nonlinear eigenvalue problems, Quart. J. Math. Oxford 24 (1973), 241 -250 | MR 333866 | Zbl 0256.47049

[24] J.F. Toland, Asymptotic linearity and a class of nonlinear Strum–Liouville problems on the half-line, Lect. Notes Math. vol. 415 , Springer (1974), 429 -434 | MR 430891 | Zbl 0321.47045

[25] J.F. Toland, Asymptotic linearity and nonlinear eigenvalue problems, Proc. R. Ir. Acad. 77 (1977), 1 -12 | MR 440109 | Zbl 0353.34022

[26] J.F. Toland, Bifurcation and asymptotic bifurcation for non-compact non-symmetric gradient operators, Proc. R. Soc. Edinb. 73 (1975), 137 -147 | MR 385658 | Zbl 0341.47042

[27] E. Zeidler, Nonlinear Functional Analysis, Springer-Verlag, Berlin (1985) | Zbl 0559.47040


text:
## 59.7 Nontorsion coefficients

To study nontorsion coefficients, one makes the following definition:

$H_{\acute{e}tale}^ i (X, \mathbf{Q}_\ell ) := \left( \mathop{\mathrm{lim}}\nolimits _ n H_{\acute{e}tale}^ i(X, \mathbf{Z}/\ell ^ n\mathbf{Z}) \right) \otimes _{\mathbf{Z}_\ell } \mathbf{Q}_\ell .$

The symbol $\mathop{\mathrm{lim}}\nolimits _ n$ denote the limit of the system of cohomology groups $H_{\acute{e}tale}^ i(X, \mathbf{Z}/\ell ^ n\mathbf{Z})$ indexed by $n$, see Categories, Section 4.21. Thus we will need to study systems of sheaves satisfying some compatibility conditions.

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# Why aren't Complex number fields used in cryptography?

Most of the cryptography is limited to use of real integer fields. Complex numbers are seldom used. Is there any reason for it? Wouldn't complex numbers provide more structure?

If there is already some work on this area, I would be happy to learn about it.

• With "complex numbers" he means "imaginary numbers" like $i^2 = -1$ – mentallurg Jun 8 '19 at 11:20
• @mentallurg OP can tell us themselves what they mean. Please don't edit other people's posts based on what you think they mean. – fkraiem Jun 8 '19 at 12:20
• @fkraiem: See the answer from "djao" below: 'I don't know what you mean by "complex number fields"'. He clearly says he does not understand the OP. – mentallurg Jun 8 '19 at 13:15
• @mentallurg It isn't clear whether the OP meant merely an analogue of the complex numbers as in a field extension with a root of $i^2 + 1$, as the phrases ‘real integer’ (in contrast, perhaps, to Gaussian integer) and ‘complex numbers’ suggest, or whether the OP meant to discuss number fields, as the phrase ‘complex number fields’ suggests. I interpreted it the first way; djao (reasonably) interpreted it the second way. Don't speak for the OP in deciding which interpretation they meant—they can speak for themselves. – Squeamish Ossifrage Jun 8 '19 at 13:35
• @girisha-shankar: Please help us :) Explain what you mean by "complex numbers". – mentallurg Jun 8 '19 at 13:39

If you mean fields of the form $$k[i]/(i^2 + 1)$$ where $$i^2 + 1$$ is irreducible over the base field $$k$$, well, they are! FourQ is a twisted Edwards curve $$-x^2 + y^2 = 1 + d x^2 y^2$$ over the quadratic extension field $$\mathbb F_{p^2} = \mathbb F_p[i]/(i^2 + 1)$$ of Mersenne prime characteristic $$p = 2^{127} - 1$$, where $$d = 25317048443780598345676279555970305165i + 4205857648805777768770$$ is nonsquare. FourQ is appealing because it takes advantage of cheap arithmetic modulo a Mersenne prime on a curve together with a cheap endomorphism. The coordinate field is in a sense the ‘complex’ extension of $$\mathbb F_{2^{127} - 1}$$ arising by adjoining a square root of $$-1$$.
(FourQ is not universally appealing: it has a relatively high cofactor, $$8\cdot7^2 = 392$$, and it does not provide modern standards of twist security, so it's not a drop-in replacement for X25519 or Ed25519. But it is implemented in practice by Microsoft's FourQlib and probably deployed somewhere.)


text:
# There does not exist group $G$ such that Aut$(G)\cong \mathbb{Z}_n$ (for odd $n$)

I had this "almost bonus" question on the final in Group Theory recently: prove that there is no such group $G$ which would satisfy Aut$(G)\cong \mathbb{Z}_n$, where $n$ is an odd integer. I don't have much certainty if this proof is OK, and one's opinion would be appreciated.

Here's my attempt:

Suppose that there exists such a group $G$ that satisfies the above condition. Since $\mathbb{Z}_n$ is cyclic, Aut$(G)$ is also cyclic and $G$ is abelian, which implies that Inn$(G)\cong \{e\}$. Thus Aut$(G)=$Out$(G)$. (I don't think this fact is important here though). Now, since an automorphism sends a generator to a generator, and since each automorphism is completely determined by such mapping, |Aut($G$)| must be of factorial order. But an integer factorial is always even. However, $|\mathbb{Z}_n|$ is odd, which is a contradiction. Therefore, no such $G$ exists.

I'm afraid that my proof is not very nice, but at least a genuine attempt was made.

• $n$ is assumed to be odd. Sorry, edited. – sequence Dec 13 '15 at 5:25
• Note that we should have $n\neq 1$, otherwise the groups of order $1$ and $2$ are trivial counterexamples. – Slade Dec 13 '15 at 20:32
• – Watson Aug 17 '16 at 10:03

$\DeclareMathOperator{\Aut}{Aut}$ We'll show the slightly stronger result that $|\Aut(G)| \not= 2n+1$ for any $n \ge 1$ EDIT: Provided $G$ is abelian: see the comments.

If $\Aut(G)$ is trivial, then there is nothing to show. Suppose, then, that $G$ has a nontrivial automorphism group. We will show that $|\Aut(G)|$ is even by explicitly exhibiting an automorphism $\phi$ of $G$ having order $2$ for any group $G$. It will then follow by Lagrange's theorem that $\Aut(G)$ has even order.

If $G$ has an element of order at least $3$, then $\phi:x \to x^{-1}$ is the desired automorphism of even order. It only remains to consider the case where $G$ contains only elements of order less than or equal to $2$. In that case, we must have that $G$ is a vector space over $\mathbb{Z}_2$ (see Group where every element is order 2 for a proof of this result). If $G$ is one dimensional as a vector space, then $\Aut(G) = \Aut(\mathbb{Z}_2)$ is trivial, so there is nothing more to show. For $G$ having dimension greater than $1$, we have that $\Aut(G) \cong \operatorname{GL}(G)$, so if we pick an ordered basis for $G$, then the automorphism which interchanges the first and second basis vectors (and fixes all others) is an order $2$ automorphism. (This argument, which Slade gave in the comments, applies even to infinite $G$, while my previous argument tacitly assumed $G$ was finite.)

• This assumes that $G$ is finite, but it is very close to applying to infinite groups as well. An abelian group in which every nonzero element has order $2$ is a vector space over $\mathbb{Z}_2$, so it has a basis and we can write $G = \oplus_i \mathbb{Z}_2$ and find lots of nontrivial automorphisms. – Slade Dec 13 '15 at 20:31
• @Slade Good point! I've changed my answer slightly to incorporate your comment. – Strants Dec 13 '15 at 20:39
• @Strants : So you are assuming $G$ is abelian ? – user228169 Apr 30 '16 at 7:41
• Every group has an element of order at most 2 (namely, the identity element). You mean a group whose every element has order at most 2 (i.e. "exponent" 2). As a matter of fact, there do exist finite groups $G$ whose automorphism group ${\rm Aut}(G)$ has odd order. The correct proof of OP's desired claim begins as follows: if ${\rm Aut}(G)$ is cyclic then so is ${\rm Inn}(G)\cong G/Z(G)$, and a standard exercise shows that if $G/Z(G)$ is cyclic then $G$ is abelian. – arctic tern Apr 30 '16 at 19:14
• @arctictern Oops, you are correct. The requirement that $G$ is abelian is necessary if $G$ has an element of order greater than $2$: otherwise, $x \to x^{-1}$ will fail to be an automorphism. I've re-edited to make it clear I'm assuming that $G$ is commutative. – Strants Apr 30 '16 at 19:20

It is not true that $|Aut(G)|=m!$ for some $m$. For example, if $G=\mathbb{Z}_5$, then $Aut(G)\cong\mathbb{Z}_4$ and 4 is not a factorial.

If you know that $G$ is abelian, then it is the product of cyclic group $G=\prod \mathbb{Z}_{p_i^{k_i}}$ where the $p_i$ are prime. It follows that $Aut(\mathbb{Z}_{p_i^{k_i}})$ is a subgroup of order $(p_i-1)p_i^{k_i-1}$ of $Aut(G)$. If $p_i$ is odd, then $p_i-1$ is even so the order of $Aut(G)$ is even. Similarly, if $p_i=2$ and $k\geq 2$ then $p^{k-1}$ is even. So you just need to check the case where $G= \mathbb{Z}_2^m$ in which unless $m=1$ (and then $Aut(G)$ is trivial), you can always find an automorphism of order 2 - for example, switch two basis elements.

Actually, it is true that $Aut(G)$ is cyclic (and not trivial) iff $G$ is cyclic of order 4, $p^k$ or $2p^k$ where $p$ is prime (see here). Using that it is easy to see that the order of $Aut(G)$ must be 2 or $(p-1)p^{k-1}$ both of which are even.

• This assumes that $G$ is finite, but the question appears to be valid even for infinite $G$. – Slade Dec 13 '15 at 20:31

Suppose that $n\geq 3$ and $n$ is odd. If $Aut(G)\cong \mathbb{Z}_n$ then $Aut(G)$ is cyclic, which implies that $G$ is abelian. But if $G$ is abelian then the inversion map $x\mapsto x^{-1}$ is an automorphism of order $2$. By Lagrange's theorem, this implies that $|Aut(G)|$ is divisible by $2$. This is a contradiction since $n$ is odd.

• The inversion map may also have order one (but of course then there are other involutionary automorphisms). – Dune Dec 7 '17 at 16:20