James F Peters Dedicated

W Dyke

I N Herstein

S V Banavar

FREE PATH RINGS AND THEIR GEOMETRIC REALIZATION AS CYCLE COMPLEXES. EXTENSION OF J.J. ROTMAN'S FREE GROUP THEOREM

Keywords: 2010 Mathematics Subject Classification. 14F35 (Homotopy theory), 32B25 (Triangulation), 57M05 (Fundamental group, presentations) Free Ring, Free Path Group, Free Path Ring, Free Ring Presentation, Homotopy, Path, Path Cycle, Realization, Vector Field

) Every 1-cycle cell complex is realizable as a path cycle and (3) Every 1-cycle is realizable as a free ring (this reverbates back to W. Dyke's 1882 work on the derivation of free groups from circuits on simply connected polygons). Inspired by Lupton-Oprea-Scoville digital fundamental groups, a number of conjectures about the geometric realization of free path rings as structures in digital images and as vector fields are given.

In this paper, Herstein rings [START_REF] Herstein | Topics in algebra[END_REF] are extended to include free rings, defined in Def. 9 with respect to a pair of homomorphisms on a free group.

From the beginning, geometry has played a key role in the introduction of free groups. A free group G(β, +) is nonempty finite set G of n elements equipped with binary operation (typically written as a +) and a basis β ⊂ G so that every member a ∈ G can be written as a linear combination the generators g ∈ β, i.e., a = g∈β kg, k mod n. Free groups were introduced by W. Dyck in 1882 as a natural biproduct of simply connected polygons P in which every vertex a ∈ P can be reached by traversing the edges between a and a distinguished vertex g ∈ P [START_REF] Dycke | Gruppentheoretischer studien[END_REF]. Later, J.H.C. Whitehead defined free groups in terms of circuits in graphs in which every every vertex can be reached in series of moves from a generator vertex [START_REF] Whitehead | On certain sets of elements in a free group[END_REF] and [START_REF]On equivalent sets of elements in a free group[END_REF]Theorem 4,p. 799] in which circuits on connected surfaces also have corresponding free groups. Polygons are simply connected, provided the polygon vertices are in a sequence of edges with no self-intersections (see Fig. 2 and Fig. 8 for examples).

This paper also introduces free path rings R(β, +, •), defined in terms of a pair of homomorphisms on a free path group (see Def. 11). Briefly, a free path group is a free group G(β, +) with a basis β ⊂ G that is a collection of paths in a path cycle and there is a homomorphism f : X × β → G. A path cycle is a collection of paths that are continuous maps h : [0, 1] → X on a space X in which the vertexes h(0), h [START_REF] Cohn | Free ideal rings and localization in general rings[END_REF] are simply connected via h ∈ G and there is no end vertex [START_REF]Path triangulation, cycles and good covers on planar cell complexes. extension of J.H.C. Whitehead's homotopy system geometric realization and E.C. Zeeman's collapsible cone theorems[END_REF], [START_REF] Peters | Descriptive proximal homotopy. Properties and relations[END_REF]App. A].

Remark 1. Applications.

Free path rings provide a topological alternative to Cohn free rings [START_REF] Cohn | Free ideal rings and localization in general rings[END_REF], useful in a number of applications, e.g., in simplified presentation of Dyck polygon cycles [START_REF] Peters | Dyck fundamental group on arcwise-connected polygon cycles[END_REF] as well as boundary cycles in maximal nucleus clusters (MNCs) of triangles covering objects in optical flow in the foreground of triangulated video frames [2, §2, p. 4].

Consideration of free path rings leads to a straightforward extension of J.J. Rotman's Free Group Theorem. For the extension, see Theorem 5.

Theorem 1. [19, p. 237] If X is a set, then there exists a group F that is free on X.

Preliminaries

This section briefly visits basic structures underlying free ring presentations of path cycles and path nerve complexes. Recall

Remark 2. Paths over Temporal Unit Intervals.

In application, it is often appropriate to consider paths over a temporal unit interval. In that case, the variable t ∈ I would be conveniently thought of as a clock tick and

grad h h(0) = ⃗ v 1 h(1) = ⃗ v 2 h Figure 1. Sample path gradient h(t) k(t ′ ) ℓ(t ′′ ) K h(0) := ℓ 0 := v 0 , t h = 0, t ℓ = 1 h(1) = k(0) := v 1 , t h = 1, t k = 0 k(1) = ℓ i (0) := v 2 , t k = 1, t ℓ = 0 k h ℓ [h, k, ℓ] △ E Figure 2. [h, k, ℓ] △ E (Curviliner path triangle) → |[h, k, ℓ] △ E| (geometric realization of [h, k, ℓ] △ E
as a curviliner triangle) on a space K. During its construction over a temporal interval, h(t), k(t ′ ), ℓ(t ′′ ) occur at times t, t ′ , t ′′ , respectively.

a path h(t) ∈ R for t ∈ [0, 1

] would depend on not only the set of points passed through by h but also the time at which a point

h(t) is visited [11, §VII.1, p. 174], i.e., h[0, 1] → X. t ∈ [0, 1], with h(t) ∈ 0 = start time, t = elapsed time, 1 =end time [0, . . . , t, . . . , 1] ,
and h(t) is an event that occurs at time t. For example, the trajectory of a moving billiard ball E traces a path h(t) with an initial time at t = 0 when the billiard starts moving, visiting a sequence of points (0-cells, or vertexes) as it travels on some surface, and end time t = 1, when E reaches an end point.

Paths provide a simple means of presenting the flow of photons in an optical flow.

Definition 2. (Optical Flow).

An optical flow is a vector field containing vectors that are photons and in which there is a circulation of light (varying directional flow of photons) reflected from a curved surface.

Example 1. (Gradient of a planar path).

Let h be a path that presents an optical flow. The gradient grad(h) describes a small movement for a vector at time t along path h, defined by

grad(h) = ∂h ∂y i + ∂h ∂x j + ∂h ∂t k.
A sample path gradient at time t is shown in Fig. 1.

In an optical flow, the gradient of the points of light varies continuously, depending on the time of day in a terrestial setting and the varying angle of reflection of the light.

A collection of path-connected endpoints on a sequence of three paths with gradients varying over time form a temporal path triangle, which is also an example of a path cycle.

Example 2. (Temporal Path Triangle).

A sample path triangle (also called a temporal path triangle) constucted over a temporal interval is shown in Fig. 2. This path triangle models the paths h 1 , h 2 , h 3 traced by a moving object such as a billiard ball during its movements before it reaches a rest state h 3 [START_REF] Cohn | Free ideal rings and localization in general rings[END_REF]. Temporal path triangles can be found in triangulated video frames [START_REF] Haider | Temporal proximities: Self-similar temporally close shapes[END_REF] in which the changing triangles on triangulated video frame shapes result from the optical flow recorded in the video.

Definition 3. Path Cycle [15, App. A].

A path cycle hCycE in a CW space K is a sequence of continuous maps {h i }

(n-1)[n] i=0 , h i : I → K, [n] = mod n, with h 0 (0) = h n[n] (0) = v 0 ∈ K, h n-1[n] (1) = v n-1[n] ∈ K. Given h i ∈ {h i } (n-1)[n] i=0
, g = h i (0), a basis element in hCycE, so that v h i+k (0) walks forward k vertexes from g to reach h i+k (0)

:= kg = kh i (0) = h i+k (0) ∈ K, k ∈ Z. hi+k (0) hi+k (0) walks back k vertexes from h i+k (0) to reach h i (0) := h (i+k)-k (0) = h i (0). + : K × K → K, is defined by +(v, v ′ ) = move to v ′ via h i (0) = v, h i+k (v ′ ) +(kg, k ′ g) = kg + k ′ g ∈ hCycE. +(v, 0) = zero moves from v, pseudo-element 0 ∈ hCycE +(kg, 0) = kg + k ′ 0 = kg = v ∈ hCycE. +(v, -v) = move back to v from v +(kg, -kg) = (k -k)g = 0g = g + 0 = v ∈ hCycE. +(v, -v ′ ) = move back to v ′′ from v ∈ hCycE +(kg, -k ′ g) = (k -k ′ )g = k ′′′ g ∈ hCycE.

Lemma 1. Let (hCycE, +) be a path cycle hCycE equipped with move +. hCycE has a basis.

Proof. From Def. 3, hCycE has at least one vertex g so that every vertex v ∈ hCycE is reachable after k moves from g. Then g is a generator element of hCycE. Hence, there is a subset β ⊂ hCycE with g ∈ β such that |β| ≥ 1, i.e., β is a basis for hCycE.

Next, observe1 that a path cycle with move + is a groupoid.

Lemma 2. Let (hCycE, +) be a path cycle hCycE equipped with move +. The

structure (hCycE, +) is a free groupoid. Proof. From Lemma 1, hCycE has a basis β ⊂ hCycE. Let g ∈ β. From Def. 3, + is a binary operation, i.e., every +(v, v ′ ) = kg + k ′ g ∈ hCycE for v, v ′ ∈ hCycE.
Hence, (hCycE, +) is a free groupoid.

A path cycle E free groupoid with basis β is denoted by hCycE(β, +).

Lemma 3. Let hCycE(β, +) be a path cycle equipped with basis β and move +. Then hCycE(β, +) is a free semigroup.

Proof. From Lemma 2, the structure hCycE(β, +) is a free groupoid with basis

β ⊂ hCycE. Let +(v, v ′ ) = kg + k ′ g for v, v ′ ∈ G, g ∈ β. Then v = kg, v ′ = k ′ g, v ′′ = kk ′′ g for v, v ′ , v ′′ ∈ hCycE, b ∈ β +((v, v ′ ), v ′′ ) = (kg + k ′ g) + k ′′ g = kg + (k ′ g + k ′′ g) = (v, (v ′ , v ′′ )).
Consequently, the operation + is associative. Hence, (hCycE, +) is a free semigroup.

Theorem 2. hCycE(β, +) is a free group.

Proof. From Lemma 3, the structure hCycE(β, +) is a free semigroup with basis β. From Def. 3, for a path cycle hCycE, each element v := kg ∈ hCycE has an inverse, namely, the -kg := v ∈ hCycE. Also, from Def. 3, hCycE has an identity element, namely, 0. Hence, hCycE(β, +) is a free group.

Remark 3. Order of a path cycle.

A k-path cycle has order k and contains k paths.

Example 3. Path cycle h E in Fig. 3 is a 3-path cycle (its order is 3) and path cycle hCycE ′ in Fig. 6 is a 9-path cycle (its order is 9).

Example 4. Path cycle h E in Fig. 4 is a 4-path cycle (its order is 3) and path cycle hCycE ′ in Fig. 6 is a 9-path cycle (its order is 9).

Definition 4. 1-Cycle. In a CW space K [23], a 1-cycle E (denoted by cycE) in a CW space K is a collection of path-connected vertexes (0-cells) on edges (1-cells) attached to each other with no end vertex.

Definition 5. (Path-Connected).

A pair of 0-cells v, v ′ in a cell complex K is path-connected, provided there is a sequence of paths h 1 , . . . , h k , starting with h 1 (0) := v and ending with

h k-1 (1) = h k (0) := v ′ .

Lemma 4. Every path has a geometric realization as an edge.

Proof. From Def. 1, a path h : I → X includes all points h(t), t ∈ [0, 1], i.e., we have the closed set of points

{h(0), . . . , h(t), . . . , h(1)} , for 0 ≤ t ≤ 1, which is geometrically realized as an edge |h| = > h(0)h(1) with h(t) ∈ int(|h|), t ∈ (0, 1) (interior of edge |h|).

Remark 4. (Significance of Lemma 4).

As a result of Lemma 4, the geometric realization of every path as an edge (a 1cell) indicates that a path also has a realization as a vector field. Recall that S. Lefschetz [7,p. 158] introduces a more general form of a Whiteadean 1-cell with an arc, which is an edge that can be either curved or straight. From an application perspective, this is significant, since we can then view a Feynman path [4, p. xiv] (a trace of a trajectory of a particle) having a geometric realization as a Lefschetz arc in which each point has both magnitude and direction, i.e., a Feynman path has a realization as a vector field. Proof.

h 1 (1) := h 2 (0) := v 2 h 1 (t) := p h 2 (t) := q h 2 (1) := h 3 (0) := v 3 h 1 (0) := h 3 (1) := v 1 h 3 (t) := r h △ E → v 1 p v 2 q v 3 r K |h △ E|
1 o : Let h E be a 3-path cycle containing paths h, h ′ , h ′′ . From Lemma 4, the geometric realization of a path h is a 1-cell (edge) |h| in a cell complex. Attach the three paths h, h ′ , h ′′ together so that

h ′ (0) := h(1) defines edge > h(1), h ′ (0) h ′′ (0) := h ′ (1) defines edge > h ′ (1), h ′′ (0) h(0) := h ′′ (1) defines edge > h ′′ (1), h(0).
From Def. 5, the vertexes are path-connected in this sequence of three edges (call it E). Hence, E is a 1-cycle that is a triangle, which is the geometric realization of h E (denoted by |h E|).

2 o : Replace h E in 1 o with a 4-path cycle containing paths h, h ′ , h ′′ , h ′′′ and the desired result follows.

3 o : Recall that a planar polytope is a convex hull that is a finite collection of intersecting half spaces [START_REF] Ziegler | Lectures on polytopes[END_REF]. Let hCycE be a k-path cycle. Replace h E in 1 o with a 4-path cycle containing paths h 1 , . . . , h k . From Lemma 4, the geometric realization of a path h is a 1-cell (edge). Assume that the geometric realization each path h ∈ hCycEis a straight edge on a half plane. Since each h i (1) = h i+1 (0) for every h i , h i+1 ∈ hCycE, the pairs of paths with geometrically-realized edges with common vertexes have geometric realizations as interseting half planes. Replace h E in 1 o with the k-path cycle hCycE and the desired result follows.

h 1 h 3 h 2 h 4 h 1 (1) := h 2 (0) := v 1 h 2 (1) := h 3 (0) := v 2 h 3 (1) := h 4 (0) := v 3 h 1 (0) := h 4 (1) := v 0 h E → v 0 v 1 v 2 v 3 K |h E|

Free Rings

This section introduces free rings, which are an extension of free groups. Recall (3) There is an element 0 ∈ R so that a + 0 ∈ R for all a ∈ R.

(4) For every a ∈ R, there is an -a ∈ R so that a + (-a) = 0.

(5

) a • b ∈ R. (6) a • (b + c) = a • b + a • c and (7) (b + c) • a = b • a + c • a.
: X × β → G defined by f (a • b) = ka • k ′ b, a, b ∈ X for every subset X in G.

Theorem 4. [13](Path Cycle Free Group Presentation).

Every path cycle in a CW space has a free group presentation.

For the structure of a path cycle, see Def. 3. Let hCycE be a path cycle. Each a ∈ G can be written as kg for g ∈ β, k ∈ Z. Also, let f : G → G, a homomorphism defined by

f (a + b) = f (a) + f (b) = kg + k ′ g = a + b = (k + k ′ )g = k ′′ g, for a, b ∈ G. Hence, from Def.

8, hCycE has a free group presentation.

A free ring R(β, +, •), introduced in this paper, is the counterpart of a free group G(β, +) with basis beta (see, e.g., [19, p. 237, 1955 edtion]. Unlike a free group, a free ring R is defined in terms of a pair of homomorphisms on a free group.

Definition 9. Free Ring.

Let G(β, +) be a free group with basis β ⊂ G and X be a nonempty set X ⊆ G, generator g ∈ β, a, b ∈ X. Then a ring R(β, +, •) is free on G, provided every map f : X × β → R has a corresponding pair of unique homomorphisms α : X × β → R with respect to + and γ : X × β → R with respect to •, kmod n ∈ Z + , defined by (X,β) G(β,+) (X,β) R (β,+,•

X ⊆ R, β ⊂ R. α(a, g) = kg ∈ R, γ(a, b) = k ′ g ∈ R, k ∈ Z. α(a + b, g) = α(a, g) + α(b, g) ∈ R for all a, b ∈ X. γ(a, g) = kg, k ∈ Z. γ(a • b) = γ(a, g) • γ(b.g) ∈ R for all a, b ∈ X.
= kg + k ′ g from Def. 9, for all a, b ∈ X, k, k ′ ∈ Z = (k + k ′ )g = k ′′ g ∈ R, k ′′ ∈ Z. γ(a • b) = γ(a, g) • γ(b.g) from Def. 9, = kg • k ′ g from Def. 9, for all a, b ∈ X, k, k ′ ∈ Z = (k • k ′ )g = k ′′′ g ∈ R, k ′′′ ∈ Z.

Free Path Rings

Free path rings are free ring structures built on free path groups.

Definition 10. Free Path Group.

A group G(β, +) with basis set β ⊆ G (a collection of paths in a path cycle hCycE) is a free path group on G, provided there is a homomorphism f :

X × β → G defined by f (h + h ′ ) = kg + k ′ g ∈ G, X ⊂ hCycE ⊂ G ⊆ hCycE, h, h ′ ∈ X for every nonvoid set of paths X ⊆ G.
Free path groups lead to free path rings, each with a structure that is similar to an ordinary free ring.

Definition 11. Free Path Ring.

A ring R(β, +, •) on a free path group G(β, +) with basis set β ⊆ G is a path free ring on G, provided there is a pair of homomorphisms α :

X × β → R defined for + by α(h + h ′ ) = kg + k ′ g ∈ R and γ : X × β → R defined for + by α(h • h ′ ) = kg • k ′ g ∈ R, X ⊂ hCycE ⊂ R, for every pair of paths h, h ′ ∈ X for X ⊆ G, g ∈ β.
In either case, a reverse move is possible, i.e.,

α(h -h ′ ) = k ′′ reverse moves from h(0) to reach h ′′ (0) kg + (-k ′ )g = (k -k ′ )g = k ′′ g = k ′′ h(0) = h ′′ (0). α(h • h ′ ) = k ′′′ reverse moves from h(0) to reach h ′′′ (0) kg • (-k ′ )g = (k • k ′ )g = k ′′′ g = k ′′′ h(0) = h ′′′ (0).
It is also the case that a free path ring has a zero move (also called the null move), serving as an identity in a free path Ring, which is possible for both + and •.

α(a + b, g) = α(a, g) + α(b, g) ∈ hRngR from Def. 9 = kg + k ′ g from Def. 9, for all a, b ∈ X, k, k ′ ∈ Z = (k + k ′ )g = k ′′ g ∈ R, k ′′ mod n ∈ Z + . γ(a • b, g) = γ(a, g) • γ(b, g)hRngR from Def. 9, = kg • k ′ g from Def. 9, for all a, b ∈ X, k, k ′ ∈ Z = (k • k ′ )g = k ′′′ g ∈ R, k ′′′ mod n ∈ Z + . v 1 v 0 v 5 = v ′ 0 = g ∈ β ⊂ R v ′ j hCycE hCycE ′ v i v 2 v 3 v 4 v ′ 1 Figure 8. Free path ring R ({hCycE, hCycE ′ : hCycE ∩ hCycE ′ ̸ = ∅} , +, •)
on a pair of intersecting path cycles hCycE, hCycE ′ . 8. In this ring, the +, • operations are defined by

Example 11. The pair of path cycles hCycE, hCycE

′ with β = hCycE ∩ hCycE ′ = {h 5 (0) = v ′ 0 = g} represent a free path ring R(β, +, •) in Fig.
h, h ′ ∈ hCycE ∪ hCycE ′ , β = hCycE ∩ hCycE ′ = {h 5 (0) = v ′ 0 = g} basis kh(0) = k moves from h(0) to reach h ′ (0) kg = h ′ (0). +(h, h ′ ) = k ′′ moves from h(0) to reach h ′′ (0) kg + k ′ g = (k + k ′ )g = k ′′ g = k ′′ h(0) = h ′′ (0). •(h, h ′ ) = k ′′′ moves from h(0) to reach h ′′′ (0) kg • k ′ g = (k • k ′ )g = k ′′′ g = k ′′′ h(0) : k ′′ ≤ k ′′ , h ′′ (0) ≤ h ′′′ (0).
In effect, •(h, h ′ ) results in a longer walk that starts at h(0) than the walk +(h, h ′ ) that starts at h(0). This is a distinguishing property of the • ring homomorphism.

Lemma 5. Every path cycle is realizable as a free path group.

Proof. Let hCycE be a path cycle, paths h, h ′ ∈ hCycE, β ⊂ hCycE, g = h(0) ∈ β. From Def. 10, we can define a homomorphism

+(h, h ′ ) = kg + k ′ g = (k + k ′ )g = k ′′ g = k ′′ h(0) ∈ hCycE.
In addition, every move +(h, h ′ ) has a reverse move -kg, i.e.. +(h,

h ′ ) = kg + (-k ′ g) = kg -k ′ g = (k -k ′ )g = k ′′ g = k ′′′ h(0) ∈ hCycE.
With k = 0, we obtain a zero move, which is the identity or null move in hCycE, i.e., +(h, h ′ ) = kg + (0g) = kg + 0 = kg = kh(0) ∈ hCycE. Hence, we obtain hCycE(β, +), a free path group on hCycE. Lemma 6. Every path cycle is realizable as a free path ring.

Proof. Let hCycE be a path cycle. From Lemma 5, hCycE is realizable as a free path group G(β, +) with basis β and homomorphism +. Similarly, hCycE is realizable as a free path group G(β, +, •) with basis β and homomorphism •. Hence, G is a free path ring.

It is a straightforward step from free path groups to free path rings.

Theorem 5. If X is a path cycle, then there exists a free path ring R that is free on X.

Proof. Let X be a path cycle. From Lemma 5, X is realizable as a free path group. In addition, from Lemma 6, X is realizable as a free path ring. Replace G(β, +) in Def. 6 with X and the desired result follows.

Theorem 6. Every path cycle is realizable as a 1-cycle.

Proof. From Lemma 4, the geometric realization of a path h is a 1-cell (edge) |h| in a cell complex. Then each of the paths in a path cycle has a geometric realization as an edge. Hence, from Def. 4 (1-cycle), a path cycle has a geometric realization as a 1-cycle.

The converse of Theorem 6 also holds.

Lemma 7. Every 1-cycle cell complex X in a CW space is realizable as a path cycle.

Proof. Let cycE be a 1-cycle on a space X. Let a, b be vertices for an edge > ab in cycE. Then define the path

h : I → X. h(0) = a. h(1) = b.
Hence, every 1-cycle in space X is realizable as a path cycle.

From an applications perspective, there is interest in the derivation of vector fields from path cycles. The importance of vector fields in algebraic topology was first pointed out by S. Lefschetz in 1949 [7, p. 17]. In an n-dimensional space X, recall that a vector field is a mapping F : 2 X → 2 X so that, for every vertex p ∈ 2 X (collection of vertexes), p has magnitude and direction, i.e., F (E ∈ 2 X ) is a collection vectors in a vector space.

Theorem 7. Every path cycle is realizable as a vector field.

Proof. Let hCycE be a path cycle. From Theorem 6, hCycE is realizable as a 1-cycle cycE. Let f : 2 X → 2 X be a mapping on a space X and let hCycE ∈ 2 X . Then, from Theorem 6, f (hCycE) = cycE, which is a collection path-connected vertexes p ∈ cycE for every h(t) ∈ hCycE. Each vertex p has a location, magnitude and direction in space R 4 . Hence, cycE is a vector field. Definition 12. A 1-cycle vector field is a 1-cycle whose members are vectors in a vector field.

Corollary 1. Every path cycle is realizable as a 1-cycle vector field.

Proof. Immediate from Theorem 7.

Theorem 8. Every 1-cycle cell complex X in a CW space is realizable as a ring that is free on X.

Proof. Let cycE be a 1-cycle on a space X. From Lemma 7, cycE is realizable as a path cycle. Then the desired result is an immediate consequence of Theorem 5. Definition 13. A vector field ring is a ring whose members are vectors in a vector field. Theorem 9. Every path cycle on a space X is realizable as a vector field ring that is free on X.

Proof. Let cycE be a 1-cycle on a space X. From Lemma 7, cycE is realizable as a path cycle. Then the desired result is an immediate consequence of Theorem 5. Remark 5. Theorem 5 is a fundamental theorem in homotopy theory, since free path rings have their counterpart in the free groups introduced by W. Dyke [START_REF] Dycke | Gruppentheoretischer studien[END_REF]. Both free path rings and free groups are a result of geometry. That is, free groups result from cycles in polygons and free path rings are realizable as 1-cycles in cell complexes. And, from Theorem 9, every 1-cycle is realizable as a free vector field ring.

Conjectures

This section briefly introduces conjectures, which lead to a transition from the results in this paper to closely related results in digital topology from G. Lupton, J. Oprea and N.A. Scoville [START_REF] Lupton | Digital fundamental groups and edge groups of clique complexes[END_REF], [START_REF] Lupton | Subdivision of maps of digital images[END_REF], e.g., Theorem 10. Theorem 5.16 [10, p.22]. Every finitely presented group occurs as the (digital) fundatmental group of some digital image.

Recall that in every triangulated digital image, there is a least one maximal nucleus cluster (MNC) of triangles on a single vertex [12, §1.4, p. 9]. By attaching the edges to the barycenters of the MNC triangles, we obtain a 1-cycle. This leads to Conjecture 1.

Conjecture 1. Every free path ring has a geometric realization as a 1-cycle in a triangulated digital image.

One way to prove Conj. 1 is to define a path over each edge between consecutive barycenters. The end result will be a path cycle, which provides a basis for a free path ring. From Conj. 1, we also have the following Conjectures. Conjecture 5. Every path cycle has a realization as a free vector field ring in a digital image.

Concluding Remark

In its introduction, this paper calls attention to geometric origins of free groups as a natural biproduct of simply connected polygons introduced by W. Dyck [START_REF] Dycke | Gruppentheoretischer studien[END_REF] and in terms of circuits in connected graphs introduced by J.H.C. Whitehead [START_REF] Whitehead | On certain sets of elements in a free group[END_REF]. It is I.N. Herstein's ring theory and Whitehead's homotopy theory that then lead to the introduction of free rings as well as free path rings in this paper. An important result in this paper is an extension of J.J. Rotman's free group theorem, namely, every path cycle is realizable as a free path ring (see Theorem 5). Another important result in this paper is that every path cycle is realizable as a vector field (see Theorem 7), leading to the introduction of free vector field rings (see Theorem 9).

Definition 1 .

 1 Path. Let I = [0, 1], the unit interval. A path in a space (S, P ) is a continuous map h : I → S with endpoints h(0) = x 0 , h(1) = x 1 ∈ P and h(t) ∈ S for t ∈ I [20, §2.1,p.11]. The geometric realization of a path h is denoted |h|.

Figure 3 .Theorem 3 .

 33 Figure 3. Three Paths that Construct the Sides of a Path Triangle h △ E in a CW space K, leading to its geometric realization |h △ E| as a 2-cell (triangle)

Figure 4 .Example 5 . 3 . 6 .Figure 5 . k ≥ 1 paths h 1 , h 2 ,Example 7 .

 45365127 Figure 4. Four Paths h 1 , h 2 , h 3 , h 4 geometrically realized as the sides of a Path Rectangle h E in a CW space K, leading to its geometric realization |h E| as a 1-cycle (rectangle)

Definition 6 .

 6 Ring [6, §7,p. 46]. A ring is a nonempty set R, a, b, c ∈ R, with operations + and • defined on R such that (1) a + b ∈ R. (2) (a + b) + c = a + (b + c).

Figure 6 .Example 9 .

 69 Figure 6. Free path ring R(β, +, •) on a free group G(β, +) with basis β. In this diagram, hook arrows represent inclusion maps, ordinary arrows represent homomorphisms and β = {v 5 = v ′ 0 = g}.

Figure 7 .Example 10 .

 710 Figure 7. Free path ring hRngR(β, +, •) on a free path group hGrpG(β, +) with basis β. In this diagram, hook arrows represent inclusion maps, ordinary arrows represent homomorphisms, and hRngR is defined on a free path group hGrpG(β, +) .

Conjecture 2 .Conjecture 3 .

 23 Every free path ring has a geometric realization in a collection of intersecting 1-cyles in a triangulated digital image. Every free path ring has a geometric realization in some triangulated digital image.

Conjecture 4 .

 4 Every free path ring has a realization as a vector field in a digital image.

Many thanks to Greg Lupton for pointing this out[8].

This diagram is a modified version of the gluing diagram introduced by Tane Vergili in[17, p.

3].

The research has been supported by the Natural Sciences & Engineering Research Council of Canada (NSERC) discovery grant 185986 and Instituto Nazionale di Alta Matematica (INdAM) Francesco Severi, Gruppo Nazionale per le Strutture Algebriche, Geometriche e Loro Applicazioni grant 9 920160 000362, n.prot U 2016/000036 and Scientific and Technological Research Council of Turkey (TÜBİTAK) Scientific Human Resources Development (BIDEB) under grant no: 2221-1059B211301223.

Conflict of Interest Statement

The author of this paper declares that there is no conflict of interest with any funding agency.


Soumen Khan

Saurabh J Pradhan

Guillaume Giraud

Françoise Bleicher

Rachel Paul

Samir Merabet

L S Shashidhara
email: ls.shashidhara@iiserpune.ac.insoumen.khan@students.iiserpune.ac.in

A micro-evolutionary change in target binding sites as a key determinant of Ultrabithorax function in Drosophila

Keywords: Ultrabithorax, ChIP-seq, high affinity binding sites, molecular evolution

Hox genes encode Homeodomain-containing transcription factors, which specify segmental identities along the anterior-posterior axis. Functional changes in Hox genes have been directly implicated in the evolution of body plans across the metazoan lineage. The Hox protein Ultrabithorax (Ubx) is expressed and required in developing third thoracic (T3) segments in holometabolous insects studied so far, particularly, of the order Coleoptera, Lepidoptera and Diptera. Ubx function is key to specify differential development of the second (T2) and T3 thoracic segments in these insects. While Ubx is expressed in the third thoracic segment in developing larvae of Hymenopteran Apis mellifera, the morphological differences between T2 and T3 are subtle. To identify evolutionary changes that are behind

the differential function of Ubx in these two insects, which are diverged for more than 350 million years, we performed comparative analyses of genome wide Ubx-binding sites between Drosophila and Apis. Our studies reveal that a motif with a TAAAT core is a preferred binding site for Ubx in Drosophila, but not in Apis. Biochemical and transgenic assays suggest that in Drosophila, TAAAT core sequence in the Ubx binding sites is required for Ubx-mediated regulation of two of its target genes studied here. CG13222, a gene that is normally upregulated by Ubx and vestigial (vg), whose expression is repressed by Ubx in T3.

Interestingly, changing the TAAT site to a TAAAT site was sufficient to bring an otherwise unresponsive enhancer of the vg gene from Apis under the control of Ubx in a Drosophila transgenic assay. Taken together, our results suggest an evolutionary mechanism by which critical wing patterning genes might have come under the regulation of Ubx in the Dipteran lineage.

Introduction

The diversification of morphology and emergent function of appendages have been important features of animal evolution. This is best exemplified in the diversity that is seen in closely related species of Arthropoda. In Bilaterians, first discovered in Drosophila melanogaster, Hox genes regulate the development of serially homologous structures along the anterior posterior axis [START_REF] Carroll | Homeotic genes and the evolution of arthropods and chordates[END_REF][START_REF] Lewis | A gene complex controlling segmentation in Drosophila[END_REF][START_REF] Mcginnis | Homeobox genes and axial patterning[END_REF].

Subsequently, large number of studies have shown that variations in Hox gene functions, due to changes in their (i) copy number, (ii) primary structure at protein levels, (iii) their expression patterns and (iv) regulation of downstream target genes, are critical for morphological diversification.

In Drosophila melanogaster, the Hox protein Ultrabithorax (Ubx) specifies the development of halteres in the third thoracic (T3) segment (for detailed review see [START_REF] Lewis | A gene complex controlling segmentation in Drosophila[END_REF][START_REF] Khan | Haltere development in D. melanogaster: Implications for the evolution of appendage size, shape and function[END_REF]. Loss of function mutations of Ubx give rise to four winged flies with complete duplication of the T2 segment in the place of T3, while overexpression of Ubx in larval wing discs leads to wing to haltere transformations [START_REF] Lewis | A gene complex controlling segmentation in Drosophila[END_REF][START_REF] Castelli-Gair | Transvection in the Drosophila Ultrabithorax gene: A Cbx1 mutant allele induces ectopic expression of a normal allele in trans[END_REF][START_REF] Cabrera | Distribution of Ultrabithorax proteins in mutants of Drosophila bithorax complex and its transregulatory genes[END_REF][START_REF] White | Contrabithorax mutations cause inappropriate expression of Ultrabithorax products in Drosophila[END_REF][START_REF] White | Regulation of the distribution of Ultrabithorax proteins in Drosophila[END_REF]. While Ubx is expressed in hindwing primordia of different insect species [START_REF] Carroll | Homeotic genes and the evolution of arthropods and chordates[END_REF][START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF], the outcome of its expression is not the same in all insect groups. In the Coleopteran Tribolium castaneum and the Lepidopteran Precis coenia and Bombyx mori Ubx is expressed only in T3 segment as in Dipteran Drosophila. Functional studies have shown that Ubx is required for the suppression of elytra and the specification of hindwings in the T3 of Tribolium [START_REF] Tomoyasu | Ultrabithorax is required for membranous wing identity in the beetle Tribolium castaneum[END_REF], it is required to specify differences in eyespot patterns between the hindwings and forewings in Precis [START_REF] Weatherbee | Uitrabithorax function in butterfly wings and the evolution of insect wing patterns[END_REF][START_REF] Matsuoka | Hox genes are essential for the development of eyespots in Bicyclus anynana butterflies[END_REF].

However, in Hymenopterans such as Apis mellifera, wherein T2 and T3 are distinguished by a marginally smaller hindwing, Ubx is expressed in both forewing and hindwing primordia [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]. The expression, however, is stronger in the hindwing primordia [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]. Over-expression of Ubx derived from A. mellifera or B. mori or T. castaneum can suppress wing development and specify haltere fate in transgenic D. melanogaster [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF], suggesting that changes in Ubx at the protein level may either have not contributed or marginally contributed to the evolution of its function. A study comparing genome-wide targets of Ubx in developing halteres of D. melanogaster and developing hindwings of A. mellifera and B. mori revealed that a large number of genes have remained common targets of Ubx in these three species [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF], which are diverged for nearly 350 million years. Among those common targets, a few wing patterning genes are differentially expressed in D. melanogaster, but not in A. mellifera or B. mori [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF].

To identify evolutionary changes in the regulatory sequences of targets of Ubx that may have brought some of the wing patterning genes under the regulation of Ubx, we performed comparative analyses of genome wide Ubx-binding motifs between D. melanogaster and A. mellifera. We find that while in Drosophila, a motif with a core TAAAT sequence (MATAAATCAY) (hereafter referred to as TAAAT motif) was enriched by Ubx in ChIP pulled-down sequences, the same was not observed in A. mellifera. Using a combination of in-vitro, cell culture and transgenic assays, our results reveal that the TAAAT motif is important (and bears greater relevance as compared to the TAAT motif) for the Ubx mediated-regulation of its target gene, CG13222, in Drosophila. We then analyzed the significance of the TAAAT motif in the Ubx mediated down-regulation of a pro-wing gene, vestigial, in Drosophila as against the TAAT motif in its orthologue in Apis. In transgenic D. melanogaster, the enhancer of vg of A. mellifera drives reporter gene expression in both wing and halteres. We show that changing the TAAT motif to TAAAT motif was sufficient to bring this enhancer of vg from Apis under the regulation of Ubx. Taken together, our study suggests that evolutionary changes in the regulatory sequences in the targets of Ubx in dipteran lineages, such as from TAAT to TAAAT as core sequence in Ubx-binding motifs, may have been an important mechanism contributing to the evolution of wing to haltere appendages.

Results

Motif with a TAAAT core sequence is enriched for direct targets of Ubx in developing halteres in D. melanogaster but not for developing hindwings in A. mellifera

Previous studies indicate that despite the differences in the hindwing morphology, the Ubx protein is expressed in the third thoracic segment of both insects (as well as other insect lineages) (Fig. 1A) [START_REF] Carroll | Homeotic genes and the evolution of arthropods and chordates[END_REF][START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]. Additionally, Ubx is highly conserved across A. mellifera, B. mori, T. castaneum, Junonia coenia and D. melanogaster at the level of its DNA-binding homeodomain and the protein interaction domains, YPWM and UbdA (Fig. S1 A). We have previously shown that overexpression of Ubx from different insect species in the wing imaginal disc of transgenic Drosophila resulted in wing to haltere transformation in a pattern similar to Drosophila Ubx [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]. A triple mutant combination of alleles, abx bx3 pbx, results in complete transformation of T3 to T2 [START_REF] Lewis | A gene complex controlling segmentation in Drosophila[END_REF]. This four-wing phenotype is rescued when Ubx is over-expressed exogenously during development using a GAL4-UAS system. This phenotype can also be rescued by expressing Ubx derived from Apis or Bombyx (Merabet, S; unpublished results ). This suggests that differences in insect hindwing morphology is a consequence of events occurring downstream of or in parallel to Ubx. Comparison of targets of Ubx between D. melanogaster, and A. mellifera suggest that many functionally important genes are common to the two lineages, although many key genes are differentially expressed between T2 and T3 in Drosophila, but in Apis [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]Fig. S1 B). This reconfirms that morphological differences may lie at the levels of regulation of those targets.

We carried out ChIP-Seq for Ubx from the third instar haltere discs (GSE205177). This method provided better resolution over earlier methods used by us [START_REF] Agrawal | Genome-level identification of targets of Hox protein Ultrabithorax in Drosophila: novel mechanisms for target selection[END_REF]others (Choo et al., 2011;[START_REF] Slattery | Cofactor binding evokes latent differences in DNA binding specificity between Hox proteins[END_REF] to identify Ubx-specific binding motifs. We then performed a comparative analysis of Ubx ChIP-Seq data generated from D. melanogaster haltere imaginal discs to Ubx ChIP-seq data generated from A. mellifera hindwing discs (reported in [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF].

De-novo motif analysis of ChIP-Seq data from D. melanogaster showed significant enrichment for a motif with a TAAAT core sequence (MATAAATCAY) (henceforth referred to as the TAAAT motif) as putative Ubx-binding site (Fig 1B). We observed that enrichment for TAAAT motif is only in Drosophila and not in Apis, while both the ChIP-Seq datasets showed enrichment for binding sites for other transcription factors such as GAGA, CTCF and Brk (Fig. 1B). We calculated the frequency of the TAAAT motif in the Drosophila dataset and found it to be 1.7X in Ubx-pulled down sequences as compared to its prevalence in the whole genome.

Interestingly, the frequency of the TAAAT motif in the entire genome was 1.8 fold higher in A. mellifera as compared to D. melanogaster (Fig. 1C), suggesting that the TAAAT motif is selectively enriched in the Ubx bound regions only in D. melanogaster and not in A. mellifera.

We also observe, similar to previous results [START_REF] Agrawal | Genome-level identification of targets of Hox protein Ultrabithorax in Drosophila: novel mechanisms for target selection[END_REF], that the canonical TAAT motif is not enriched in Ubx-pulled down sequences, rather it was found underrepresented compared to its prevalence in the whole genome (Fig. 1C). This was found to be true for both Drosophila and Apis datasets.

The TAAAT motif is critical for Ubx mediated regulation of a target gene in Drosophila halteres Our results suggest that the TAAAT motif is enriched in Ubx-pulled down sequences from haltere imaginal discs of Drosophila, but not from developing hindwings of A mellifera. Earlier studies have reported that the TAAAT motif is bound by the Ubx-Extradenticle-Homothorax complex [START_REF] Slattery | Cofactor binding evokes latent differences in DNA binding specificity between Hox proteins[END_REF][START_REF] Sánchez-Higueras | In vivo Hox binding specificity revealed by systematic changes to a single cis regulatory module[END_REF]). However, neither Extradenticle (Exd) nor Homothorax (Hth) are expressed or required for the development of the haltere capitellum [START_REF] Casares | A dual role for homothorax in inhibiting wing blade development and specifying proximal wing identities in Drosophila[END_REF]. In this context, we sought to determine the functional significance of Ubx-binding to the TAAAT motif during haltere development.

We first compared Ubx ChIP-seq data from Drosophila halteres to RNA seq data (GSE205352) for Drosophila wing and haltere imaginal discs to identify those direct targets that are upregulated or downregulated in the haltere. We then compared the frequency of the TAAAT motif in Ubx bound response elements of putative direct targets that are upregulated or downregulated between wing and haltere discs. We found the frequency of the TAAAT motif in Ubx bound response elements in the upregulated category is marginally higher (1.4 times) as compared to the downregulated category (Table S2) . This suggests that while the TAAAT motif may be preferred site for Ubx to bind on the enhancers of its targets, Ubx may use this motif to regulate both upregulated and downregulated targets in the haltere.

We next evaluated the affinity and functional importance of Ubx binding to the TAAAT motif in one of the well characterized targets, CG13222, which is upregulated by Ubx in developing halteres [START_REF] Mohit | Modulation of AP and DV signaling pathways by the homeotic gene Ultrabithorax during haltere development in Drosophila[END_REF][START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF]. The "edge" enhancer of CG13222 has two TAAT motifs at 17 bp apart (CG13222_WT, Fig 2A). [START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF] have named the two motifs as site 1 and site 2. In their transgenic assays, site1 appears to be critical for Ubx-mediated regulation of CG13222, while site2 is dispensable. Interestingly, the site1 in the edge enhancer, which is critical for its regulation by Ubx, has a TAAAT motif which overlaps with the TAAT motif (Fig. 2A). Their analysis of site1 involved mutating both TAAT and TAAAT motifs, which leads to loss of enhancer driven reporter gene expression [START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF]).

We mutated site1 in such a way that the mutant enhancers carry either the TAAAT motif (CG13222_M1_A) or the TAAT motif (CG13222_M1_B) (Fig. 2A).

To examine the relative affinities of Ubx binding to the TAAAT and TAAT sites by Electrophoretic Mobility Shift Assay (EMSA), we used a 21bp long probe covering site 1 of edge enhancer of CG13222 (nucleotide stretch in the grey box in Fig. 2A). We find that Ubx can bind to the wild type probe derived from the CG13222 edge enhancer. Mutations in the TAAAT motif in site1 of CG13222 lead to a substantial loss of this binding (probes CG13222_M1_A, Fig. 2B). Conversely, mutating the TAAT motif alone had no significant effects on binding of Ubx to the probe (CG13222_M1_B, Fig S2 A).

We also observed that another Hox protein, Scr, was unable to bind to the wildtype probe CG13222. On the other hand, both Ubx and Scr bind to a 29bp probe derived from the sal enhancer (Galant et al. 2002) containing TAAT sites (Fig 2B). Perhaps, the TAAAT motif provides higher specificity of binding for Ubx as compared to other Hox proteins.

Next we examined the importance of the TAAAT motif in gene regulation using Luciferase reporter assays in S2 cells and haltere imaginal discs in transgenic Drosophila. For these functional assays, we used a 512bp long region spanning the edge enhancer of CG13222 as reported by [START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF], which has both site1 and site2. Consistent with CG13222 being a target of Ubx upregulated during haltere development, in the presence of Ubx a luciferase expression construct driven by the enhancer of the gene was significantly upregulated (2.8 folds) in S2 cells (Fig. 2C). Using a similar experimental design, we observed a significant decrease in Ubx-dependent expression when TAAAT alone is mutated (construct CG13222_M1_A in Fig. 2C) compared to the wildtype CG13222 enhancer.

We next generated transgenic strains of D. melanogaster carrying the wild type or mutant enhancers (as explained above) cloned upstream of a GFP reporter. The wildtype CG13222 enhancer showed GFP expression at the posterior edge of the haltere imaginal discs consistent with earlier reports (Fig. 2D) [START_REF] Mohit | Modulation of AP and DV signaling pathways by the homeotic gene Ultrabithorax during haltere development in Drosophila[END_REF][START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF]). We first replicated the mutation described in [START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF] wherein both the TAAT and TAAAT motifs are mutated (CG13222_M1) and found that the reporter gene expression is significantly reduced when driven by the mutant enhancer (Fig. 2E). We then analysed the CG13222_M1_A mutant where the TAAAT motif is specifically mutated while the TAAT motif is maintained intact and observed a significant loss of reporter expression (Fig. 2F,2H).

However, the pattern of GFP expression patterns driven by CG13222_M1 and CG13222_M1_A enhancers were similar, suggesting that the TAAAT motif is specifically required for Ubx-mediated activation of the CG13222 enhancer in Drosophila halteres.

As described earlier, the edge enhancer of CG13222 has a second TAAT motif (site2 in Fig 2A ), which is redundant for Ubx-mediated upregulation of CG13222 in the haltere discs [START_REF] Hersh | The UBX-regulated network in the haltere imaginal disc of D . melanogaster[END_REF]). We also attempted to examine the effect of mutating the TAAT motif to a TAAAT motif (in site2, construct CG13222_M2_A), which results in two high-affinity binding motifs in the edge enhancer of CG13222. We observed a significant reduction in the luciferase activity (Fig. S2 B), perhaps, due to negative effect of two high-affinity binding sites for Ubx in close proximity. However, the Drosophila transgenic line carrying the same mutation showed significantly stronger expression of the GFP reporter (Fig 2G ,2H) compared to the wildtype CG13222 enhancer. Enhancer driven expression was also observed in ectopic regions in the posterior compartment (red arrows in Fig. 2G), suggesting that the presence of an additional TAAAT motif may bring the otherwise unresponsive site2 under Ubx regulation.

The TAAAT motif causes Ubx mediated repression of an orthologous enhancer of the vestigial gene from A. mellifera in a transgenic Drosophila assay

We had previously reported that several wing patterning genes such as the vestigial (vg) gene are expressed in both fore-and hindwings primordia in A. mellifera. On the contrary, in Drosophila, vg is a direct target of Ubx (Suppl. 2C) and is downregulated in the developing halteres [START_REF] Galant | Hox repression of a target gene: extradenticleindependent, additive action through multiple monomer binding sites[END_REF][START_REF] Hersh | Direct regulation of knot gene expression by Ultrabithorax and the evolution of cis-regulatory elements in Drosophila[END_REF]. Of the two well characterized enhancers, the quadrant enhancer of vg (henceforth named as quad-vg) is differentially expressed between the wing and haltere imaginal discs. In a transgenic Drosophila assay, an enhancer of vg from Apis (henceforth named as Apis-vg) equivalent to quad-vg showed similar patterns and levels of expression between wing and haltere discs (Prasad, Tariekre et al. 2016), suggesting that Drosophila Ubx too cannot repress the Apis-vg enhancer. We evaluated the role of TAAAT in Drosophila as against TAAT in Apis in the regulation of the quad-vg and Apisvg enhancers in transgenic assays.

We first scanned the entire 850bp sequence of the quad-vg enhancer and the 575bp sequence of the Apis-vg enhancer for Ubx binding motifs, TAAAT and TAAT. We observed a 25bp cassette containing both TAAT and TAAAT motifs in the quad-vg enhancer (Fig 3A). In the Apis-vg enhancer, we found only a single TAAT motif and did not find any TAAAT motif (Fig 3A). In an attempt to test the significance of this difference in Ubx binding motifs between the two enhancers, we generated several Drosophila transgenics carrying the wild-type and mutated quad-vg and Apis-vg constructs (mutations in TAAT or in TAAAT motifs) upstream of a GFP reporter (Fig 3A,Suppl. Fig 2D,Suppl. Fig 3A). As reported earlier, we observed that the wild type quad-vg enhancer drives expression of the GFP reporter in the wing imaginal discs, albeit at much lower levels (compared to earlier reported quad-vg -lacZ reporter), but not in the haltere imaginal discs (Suppl. We next analysed the reporter GFP expression in wing and haltere imaginal discs of Drosophila transgenics carrying the wild type and mutated Apis-vg enhancers. As reported earlier [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF], we observed similar expression of GFP in both wing and haltere imaginal discs (Fig. 3B). Interestingly, in a chimeric enhancer (Apis-vg_M2), where the 25bp Ubx-binding cassette from the Drosophila quad-vg enhancer replaced its counterpart in the Apis-vg enhancer (Suppl. Fig. 3A (iii)), we observed differential expression of the GFP reporter between wing and haltere imaginal discs (Suppl. Fig. 3B). Its expression was much lower in the haltere pouch compared to the GFP reporter driven by the wildtype Apis-vg enhancer. The loss of reporter GFP expression in the pouch region was consistent across all mutant Apis-vg constructs which bore a TAAAT motif but was not observed in constructs where the TAAAT motif was absent (Suppl Fig 3A (vi), 3B). More importantly, changing only the TAAT motif of the Apis-vg enhancer to a TAAAT motif (Apis-vg_M1), was sufficient for the repression of the GFP reporter in the pouch (Fig. 3C Taken together, our results reveal that a microevolutionary change in the enhancer sequence, specifically modifying the TAAT motif to a TAAAT motif, may have brought certain critical wing-patterning genes, such as the pro-wing gene vg, under the regulation of Ubx during the evolution of dipterans.

Discussion

Genetics, cell and molecular biology methods have established, unequivocally, the role of Hox genes as master control genes in regulating segment-specific developmental pathways and diversification of body plans during evolution. However, precise mechanism by which orthologous Hox proteins mediate differential development of a specific morphological feature in different species is still largely unknown. Main reasons this has eluded systematic study include their highly conserved DNA-binding domains across all species.

In Drosophila, the Ubx protein is expressed in the T3 segment and specifies the development of the haltere by activating or repressing a number of genes at various hierarchical levels of wing patterning [START_REF] Weatherbee | Ultrabithorax regulates genes at several levels of the wing-patterning hierarchy to shape the development of the Drosophila haltere[END_REF][START_REF] Shashidhara | Negative Regulation of Dorsoventral Signaling by the Homeotic Gene Ultrabithorax during Haltere Development in Drosophila[END_REF]. Ubx is also expressed in the T3 segment of other insect species and thought to specify different fates in each of them. For example, in Coleopterans, Ubx specifies the development of hindwings instead of elytra and in Lepidopterans it specifies differences in eyespot patterns between the forewing and hindwings. In more ancestral Hymenopterans such as Apis mellifera, which have two pairs of wings, hindwings are marginally smaller than the forewings. In A. mellifera, Ubx is expressed in both forewing and hindwing primordia, although its expression is stronger in T3 [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]. It is possible that divergence of Coleopterans, Lepidopterans and Dipterans involve both suppression of Ubx expression in T2 and Ubx acquiring ability to regulate various developmental pathways in T3.

To identify the mechanisms governing the differential regulation of wing patterning genes between T2 and T3 in Drosophila, we employed a comparative genomics approach and identified that the TAAAT motif is enriched by Ubx specifically in the enhancers of targets of Ubx in Drosophila halteres but not in Apis hindwings. Our functional studies reported here suggest that Ubx binds to the TAAAT motif with higher affinity than to the TAAT motif and its binding to former is critical for the up-regulation of CG13222 expression in the haltere imaginal discs.

An earlier report of ours [START_REF] Prasad | A comparative genomic analysis of targets of Hox protein Ultrabithorax amongst distant insect species[END_REF]) and this report suggest that unlike the quad-vg enhancer of Drosophila, an enhancer of vg gene of A. mellifera is not differentially expressed, but drives GFP expression in both wing and haltere imaginal discs in a transgenic assay. We show that changing the TAAT motif to TAAAT motif, dramatically, brought the enhancer under the negative regulation of Ubx. The Apis-vg enhancer, thus, allowed us to dissect the importance of TAAAT motif in dipteran evolution. As vg is a pro-wing selector gene and can assign wing fate to any group of dorsal epithelial cells [START_REF] Kim | Integration of positional signals and regulation of wing formation and identity by Drosophila vestigial gene[END_REF][START_REF] Klein | Different spatial and temporal interactions between Notch, wingless, and vestigial specify proximal and distal pattern elements of the wing in Drosophila[END_REF][START_REF] Williams | Control of Drosophila wing and haltere development by the nuclear vestigial gene product[END_REF][START_REF] Neumann | A hierarchy of cross-regulation involving Notch, wingless, vestigial and cut organizes the dorsal/ventral axis of the Drosophila wing[END_REF], it is a critical target of Ubx to specify haltere development. In this context, a microevolutionary change (TAAT to TAAAT motif) in the enhancer of an ancestral vg may be a critical step in the evolution of dipterans.

It is, however, very unlikely that a large number of convergent mutations would be involved in this process, wherein multiple TAAT motifs are evolved to TAAAT motifs. A few critical genes, such as vg, upstream of wing patterning pathways may have evolved to become targets of Ubx through this route. Once regulatory networks of those genes are modulated by Ubx, chromatin landscape of many other targets (Ubx may bind to these targets via TAAT motifs) would change making them amenable for Ubx-mediated regulation and thereby specifying the haltere fate. In addition, certain co-factors influencing Ubx-mediated regulation of its targets irrespective of Ubx binds to TAAAT or TAAT motif cannot be ruled.

Materials and Methods

1.

ChIP sequencing: Third instar wandering larvae were cut, inverted and fixed with 1.5% PFA (ThermoFisher scientific) for 20 minutes at room temperature and subsequently quenched (125mM Glycine solution, 1XPBS). Samples were washed twice with 1XPBS (Sigma) for 10minutes each and dissected for wing and haltere discs (500 number of wing discs and 1000 number of haltere discs were used per replicate). Samples were lysed with Cell Lysis Buffer (10mM Tris-Cl pH 8, 10mM NaCl, 0.5% NP40, 1xPIC (Roche)) followed by mechanical shearing for 10minutes on ice. After centrifugation at 2000rpm for 10mins at 4 o C, the was pellet resuspended in Sonication buffer (50mM Tris-Cl pH 8, 1% SDS, 1% NP40, 10mM EDTA, 1xPIC) followed by incubation on ice for 30 minutes. Sonication was carried out using the Covaris S2 sonicator using settings (DC 20%, Intensity 5, Cycles of Burst 200, Time= 20 minutes). Samples were centrifuged at 14000rpm for 15mins at 4 o C and precleared using with ), and once with TE buffer (10mM Tris-Cl pH 8, 500mM EDTA). Samples were eluted in elution buffer (50mM Tris-Cl, 1mM EDTA, 1% SDS, 50mM NaHCO3). Samples were decrosslinked followed by treatment with RNAse treatment at 37 degrees for 1hour and Proteinase K treatment at 42 o C for 2 hours. DNA was purified using PCI purification and quantified using the Qubit HS DNA quantification system.

For library preparation, equal amount of DNA (~2 ng) was used as an input for NEB Ultra II DNA library prep kits (NEB #E7645). Number of cycles for amplification of adapter ligated libraries were estimated by the qPCR before final amplification to avoid any bias arising due to PCR amplification and indexing (NEB #E7350). Final amplified libraries were purified twice, first with 1X followed by 0.8x volume of beads per sample using HiPrep PCR clean up system (Magbio #AC-60050). Library concentration was determined using Qubit HS DNA kit (Invitrogen #E7350) and average fragment size was estimated using DNA HS assay on bioanalyzer 2100 (Agilent #5067-4626) before pooling libraries in equimolar ratio. Sequencing reads (100bp PE) were obtained on the Hiseq 2500 V4 platform at Macrogen Inc, Korea.

ChIP sequencing analysis:

For D. melanogaster, raw reads were trimmed using the Trimmomatic software (command) and aligned to the dm6 genome (version BDGP6.28). Peak calling was performed using MACS2 (maxdup=1, FDR 0.01) [START_REF] Zhang | Model-based analysis of ChIP-Seq (MACS)[END_REF]) and high confidence peaks (occurring in at least two biological replicates) were identified (https://roche.info/articles/2018-07-11-chip-seq-consensus). For Apis mellifera, raw fastq reads were downloaded from NCBI (GSE71847). Reads were aligned to the Amel_4.5 genome (version 4.5.47) and peak calling done using MACS2 (maxdup=1, FDR 0.01). High confidence peaks occurring in both replicates were identified. Peaks were annotated to their nearest TSS using the Homer software (annotatePeaks.pl) [START_REF] Heinz | Simple Combinations of Lineage-Determining Transcription Factors Prime cis-Regulatory Elements Required for Macrophage and B Cell Identities[END_REF]. Gene ontology of targets was performed using GO [START_REF] Ashburner | Gene Ontology: tool for the unification of biology[END_REF][START_REF] Carbon | The Gene Ontology resource: Enriching a GOld mine[END_REF]) and overrepresented GO terms plotted. The ChIPseeker program [START_REF] Yu | ChIP seeker: An R/Bioconductor package for ChIP peak annotation, comparison and visualization[END_REF] was used to annotate peaks to genomic regions. Genome tracks were made using Deeptools (normalizeUsing RPGC, binsize 1, minMappingQuality 10, smoothLength 150) [START_REF] Ramírez | deepTools2: a next generation web server for deep-sequencing data analysis[END_REF]) and visualized using the IGV software [START_REF] Robinson | Integrative genomics viewer[END_REF]. Heatmaps were generated using Deeptools (referencePoint TSS).

RNA seq data generation and analysis:

Third instar wandering larvae of the Canton S strain were collected, cut, inverted and dissected for wing and haltere discs in cold PBS.

Experiments were carried out in triplicates and samples were snap frozen in Trizol. Library preparation and sequencing on Illumina Hiseq2000 was performed at Genotypic Technology, Bangalore, India. Raw fastq files were obtained and used for analysis. Raw reads were trimmed using Trimmomatic and aligned to the reference genome using the Hisat2 software (Kim et al. 2015, 2) followed by read counts using the Htseq software [START_REF] Anders | HTSeq--a Python framework to work with high-throughput sequencing data[END_REF].

Differentially expressed genes were identified using the edgeR software [START_REF] Robinson | edgeR: a Bioconductor package for differential expression analysis of digital gene expression data[END_REF]) using 1.5 fold difference as the cut-off.

Motif analyses and protein sequence comparison:

De-novo motif analysis was carried out using Homer (findMotifsGenome.pl). The PWM for the TAAAT motif obtained from Homer was converted to Transfac format using RSAT [START_REF] Nguyen | RSAT 2018: Regulatory sequence analysis tools 20th anniversary[END_REF]) and finally converted to MEME format using transfac2meme command. Identification of binding motifs in enhancers of CG13222, quad-Vg and ApisVg was performed using the MAST software from MEME suite [START_REF] Bailey | MEME Suite: Tools for motif discovery and searching[END_REF].

Protein sequences of Ubx from different insect species were downloaded from Uniprot and multiple sequence alignment performed using Clustal Omega [START_REF] Madeira | The EMBL-EBI search and sequence analysis tools APIs in 2019[END_REF].

Alignments were visualised and processed using the Jalview software [START_REF] Waterhouse | Jalview Version 2-A multiple sequence alignment editor and analysis workbench[END_REF].

5. Frequency calculation of TAAAT motif in Ubx response elements: Using a 1.5 fold difference (FD) cut-off, genes that are upregulated or downregulated in the haltere imaginal discs were identified. Ubx targets obtained from ChIP-seq were mapped to differentially expressed genes to identify putative Ubx response elements that are upregulated, downregulated or not-differentially expressed in the halteres. The PWM of the TAAAT motif was generated and its frequency calculated in each group of Ubx response elements using the FIMO software.

Plasmids constructs, cloning and transgenic fly generation:

The full list of primers as well as sequences of enhancers of the CG13222, quad-Vg and ApisVg is provided as supplementary data (File S2). For Luciferase assays, site-directed mutagenesis was used to clone enhancer constructs of the CG13222 gene between Kpn1 and Nhe1 restriction sites, upstream of a modified pGL3 vector containing a 5X Dorsal binding site. Metallothionein inducible pRMHa3 vectors containing Ubx were previously generated in the lab and empty pRMHa3 vector was generated by excising the cloned Ubx sequence. For generating transgenics, all enhancer constructs were cloned between the Nhe1 and Kpn1 restriction sites of the pH-stinger-attb (a kind gift from Manfred Frasch) and injected into the attp40 site on the second chromosome using a mini white screen at NCBS fly facility, Bangalore. All constructs were sequence verified before use in functional assays. Insertion of various transgenes in attp40 site helped for better comparison of wildtype and mutant transgenes of a given enhancer.

7. Luciferase assays: S2 cells were checked for contamination before performing Luciferase assays. Cells were plated onto 24 well plates at a density of 3*10^5 cells per well 6 hours prior to transfection. For every construct, either wild type or mutant, two sets of experiments were designed; one well was co-transfected with the enhancer construct in pGL3 vector and the empty pRMHa3 vector whereas the other well was co-transfected with the enhancer construct and pRMHa3 vector containing Ubx. Renilla luciferase was used as an internal control and co-transfected in all experiments. Transfection was carried out using the Effectene transfection reagent and all experiments carried out in 3 technical replicates and at least 3 biological replicates. 48 hours post transfection, sterile CuSO4 solution was used to induce expression of Ubx at a final concentration of 500um and incubated for 24 hours. Cells were harvested, pelleted down (1000rpm for 4mins) and 100ul of 1X Passive Lysis buffer added and vortexed to dissolve the cell pellet. Cells were incubated for 15mins at room temperature and further spun at 10,000rpm for 90secs to collect the supernatant. The luminescence was measured with the Dual-glo Luciferase assay kit (Promega) on Ensight Plate reader (Perkin Elmer). All readings were normalized to Renilla luminescence and datasets compared using the Prism software.

8. EMSA: VC-Ubx and VC-Scr were cloned in the PcDNA3 vector and produced with the TNT-T7-coupled in vitro transcription/translation system (Promega) for EMSAs, as previously described [START_REF] Hudry | Hox proteins display a common and ancestral ability to diversify their interaction mode with the pbc class cofactors[END_REF]). Shortly, between 3 and 6 microliters of programmed lysate was used for each protein (100 ng/ml of proteins were produced on average). The VC-Ubx and VC-Scr fusion proteins were produced separately (0,5mg of each plasmid was used for the in vitro transcription/translation reaction). Supershift against the VC fragment was performed by adding the anti-GFP antibody after 15 minutes in the binding reaction. Each band shift experiment was repeated at least two times. 9. Immunostaining and Microscopy: Wandering third instar larvae were cut and inverted in cold PBS followed by fixation with 4% PFA for 20mins with gentle rocking. Samples were washed thrice with 0.1% PBTX (0.1% Triton in PBS) for 10 minutes each, followed by one hour of blocking at room temperature (blocking solution: 0.5% BSA in 0.1%PBTX). Samples were incubated with primary antibodies (dilutions made in blocking solution) at 4 o C overnight followed by washing with 0.1% PBTX for 10mins (x3) at room temperature. Samples were incubated with secondary antibodies for one hour at room temperature, washed with 0.1% PBTX for 10mins (x3) and finally with PBS before mounting. Wing and haltere imaginal discs were dissected out, mounted using Prolong Gold Antifade (Invitrogen) and stored at 4 degrees. Antibodies used in the study are Rb-GFP (1:1000) (Invitrogen), Rb-Ubx (1:1000) [START_REF] Agrawal | Genome-level identification of targets of Hox protein Ultrabithorax in Drosophila: novel mechanisms for target selection[END_REF], m-Ubx (1:30) (DSHB), goat-Hth (1:100) (Santa Cruz Biotechnology), Alexa Fluor 568 (1:1000) (Invitrogen) and Alexa Fluor 633 (1:1000) (Invitrogen). All images were taken on Leica Sp8 system at Microscopy Facility, IISER Pune. Laser settings (Laser Power (LP) and Gain (G)) used for measuring GFP fluorescence have been indicated for each image panel. All images were processed using the ImageJ software and compiled using Microsoft PowerPoint and Adobe Illustrator. For Luciferase and Transgenic assays, the entire 512bp spanning the CG13222 edge enhancer was used. B) While both Ubx and Scr bind to TAAT motif of sal, only Ubx binds to TAAAT motif of CG13222_WT (site1). Binding of Ubx to CG13222_WT (site1) is severely reduced when the TAAAT motif is mutated to TAAT motif (CG13222_M1_A), whereas no such effect is seen on mutating the TAAT motif (CG13222_M1_B).

Figures and

C) The CG13222 enhancer drives Luciferase activity in a S2 cell culture system in presence of Ubx. Significant loss of reporter activity is observed in the mutant enhancer (CG13222_M1_A)

where the TAAAT motif is affected. For statistical analysis, t-test was performed (two-tailed).

D-H).

The CG13222 enhancer drives reporter expression in the posterior edge of the third instar haltere imaginal discs (D). The CG13222_M1 mutant where both the TAAT and TAAAT motifs are affected show a marked reduction in reporter expression (E). The CG13222_M1_A mutant carrying changes in the TAAAT site of the enhancer has a similar phenotype as the CG13222_M1 mutant (F) and shows a significant reduction in GFP expression as seen from calculation of average fluorescence intensity (H). In the CG13222_M2_A enhancer where the TAAT is mutated to TAAAT in site2 results in significantly higher level of reporter expression (H) along with ectopic expression in some domains (shown by red arrows) (G). For statistical analysis, t-test was performed (two-tailed). Apis-vg_M1 transgenics. For statistical analysis, t-test was performed (two-tailed).

  Fig 2E). However, owing to complete loss of enhancer readout in both wing and haltere imaginal discs in the transgenic carrying mutations in the TAAAT motif of the quad-vg enhancer (Suppl. Fig 2E), we were unable to conclude the role of the TAAAT motif or the TAAT motif in Ubx mediated regulation of the quad-vg enhancer.

  , 3D,Suppl. Fig 3B) of haltere discs without affecting its expression in the wing pouch (Suppl. Fig 3C).

  4ml of Magnetic A Beads (Diagenode) at 4 o C for 1 hour. Preclearing beads were removed and 2ml of Polyclonal anti-Ubx antibodies (Agrawal et al. 2011) were added with overnight incubation at 4 o C. Magnetic A beads were added and incubated for 4 hours at 4 o C. The supernatant was removed and beads washed twice with low salt buffer (20mM Tris-Cl pH 8, 150mM NaCl, 0.1 % SDS, 2mM EDTA, 1% TritonX-100), twice with High Salt buffer (20mM Tris-Cl pH 8, 500mM NaCl, 0.1 % SDS, 2mM EDTA, 1% TritonX-100), twice with LiCl buffer (10mM Tris-Cl pH 8, 250mM LiCl, 1% NP40, 1% Na-Deoxycholate, 500mM EDTA,

Figure 1 :

 1 Figure 1: Motif with a TAAAT core sequence is enriched in direct targets of Ubx in developing halteres in D. melanogaster but not in developing hindwings in A. mellifera

Figure 2 :

 2 Figure 2: The TAAAT motif is critical for Ubx mediated regulation of a target gene in Drosophila halteres

Figure 3 :

 3 Figure 3: The TAAAT motif causes Ubx mediated repression of an orthologous enhancer of the vestigial gene from A. mellifera in a transgenic Drosophila assay

Acknowledgments

We thank G. Deshpande and members of the LSS and SM laboratories for critical input. We thank S. Galande for providing reagents for Library preparation. This work was supported primarily by an Indo-French Research grant from CEFIPRA to SM; a JC Bose Fellowship and grant from the Department of Science and Technology, Government of India to LSS; and a Council of Scientific & Industrial Research (CSIR) Fellowship to SK.

Data availability: Raw fastq files of ChIP sequencing for the Ubx protein in Apis mellifera hindwings can be accessed from NCBI (GSE71847). Raw fastq files of ChIP sequencing for the Ubx protein in Drosophila melanogaster halteres and RNA sequencing data for wing and haltere imaginal discs can be accessed from NCBI (GSE205177 and GSE205352).

Author contributions:

SK carried out all fly experiments, image analyses, and wrote the MS.

SK and SP did ChIP-Seq and RNA-Seq and analyses. GG, FB and RP did EMSA experiments.

LSS and SM conceived the project and wrote the MS.

We declare "no-conflict-of-interest".