{'fraction_non_alphanumeric': 0.04589913397860418, 'fraction_numerical': 0.02098828323993887, 'mean_word_length': 3.788048780487805, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Double-interval societies

Consider a society of voters, each of whom specify an approval set over a linear political spectrum. We examine double-interval societies, in which each person's approval set is represented by two disjoint closed intervals, and study this situation where the approval sets are pairwise-intersecting: every pair of voters has a point in the intersection of their approval sets. The approval ratio for a society is, loosely speaking, the popularity of the most popular position on the spectrum. We study the question: what is the minimal guaranteed approval ratio for such a society? We provide a lower bound for the approval ratio, and examine a family of societies that have rather low approval ratios. These societies arise from double-n strings: arrangements of n symbols in which each symbol appears exactly twice.


Introduction
Consider the voting model of Berg et. al. [1] in which a political spectrum X is viewed as a continuum, with liberal positions on the left and conservative positions on the right, and in which each voter v "approves" an interval of positions along this line. For example, a tolerant moderate might approve a wide interval near the middle of the line, while an intolerant partisan may approve a narrower interval near one of the ends.
More formally, a society is a spectrum X together with a set of voters V and a collection of approval sets {A v }, one for each voter. A point on the spectrum X is called a platform. In our situation, we imagine X to be R, and each approval set A v is a closed interval that represents the set of all platforms that v approves. Now suppose that every pair of people can agree on some platform; that is, their intervals overlap. In this situation, Helly's Theorem [3] implies that there exists a point on the line that lies in everyone's approval set, i.e., there is a platform that everyone approves. Thus a strong hypothesis (pairwise intersecting sets) produces a strong conclusion (a point in all the sets). However, in voting theory, we are usually not looking for unanimity, but may be satisfied with a platform that has high approval ratio: the fraction of voters that approve this platform.
Various authors have relaxed the hypotheses. Berg et. al. [1] define a linear (k, m)-agreeable society in which voter preferences again are modeled by closed intervals in R 1 . In this society, given any set of m voters, there exists a subset of k voters whose approval intervals mutually intersect. They prove that there must exist some platform with approval ratio k−1 m−1 . Another generalization by Hardin [2] looks at approval intervals on a circle rather than a line, and finds that with (k, m)-agreeability, the approval ratio of the society is at least k−1 m .
A We generalize the one-interval model to a society in which every member is identified with two disjoint approval intervals and call such a society a doubleinterval society. This situation may arise naturally in the context of voting to account for voters who do not place candidates along a linear spectrum in exactly the same order, or to account for voters who find disjoint sets of platforms appealing for entirely different reasons (e.g., for being a party purist, or having the ability to work across party lines). In a scheduling context, such intervals might model a society of workers, each of whom has two different work shifts. Figure 1 illustrates a double-interval society with four voters. The approval sets of each voter have been separated vertically so they are easier to see. Note that the approval sets are pairwise-intersecting: each voter overlaps every other voter in one or both of their approval intervals. In this example, there are several platforms approved by three voters, but no platform is approved by all four. The approval number of a platform a(p) is the number of voters (in a society S) who approve of platform p. The approval number of a society a(S) is the maximum approval number over all platforms in the spectrum X. That is a(S) = max p∈X a(p).
Finally, define the approval ratio of a society to be the approval number of S divided by the number of voters in S.
The main question we address in this paper is: what is the minimal approval ratio of a pairwise-intersecting, double-interval society with n voters?
Examples suggest that the minimal approval ratio of such societies is 1/3; that is, there is always a platform that will get at least a third of the votes. Our results in this paper attempt to clarify this intuition.
We will first examine a family of double-interval societies with low approval ratios that have regular patterns of interval overlap. These arise from the construction of what we call double-n strings, defined in the next Section. The combinatorics of such strings are quite nifty and provide a lower bound for the approval ratio of societies in this family (Theorem 3.6) as well as an upper bound (Theorem 3.7) for societies in this family. Roughly speaking, the double-n strings produce societies with asymptotic approval ratios between 0.348 and 0.385.
We will also prove a general lower bound for the approval ratio of any pairwiseintersecting, double-interval society in Theorem 4.1, which shows the approval ratio is always greater than 0.268.
Then we ask if we can find specific societies with lower approval ratios than the ones arising from double-n strings, and discover that there are such examples. We find them by modifying the construction that comes from double-n strings. See Table 1. However, all of these examples have approval ratio greater than or equal to 1/3.

Double-n String Societies
Double-interval societies with regular patterns of interval overlap can be represented by double-n strings, that is, strings of length 2n containing exactly two occurrences of each of n symbols. At times we will also represent double-n strings as strings of the symbols 1, . . . , n. We define the distance between two distinct symbols in a double-n string to be the minimum distance between a pair of occurrences of the symbols, where the distance between two adjacent symbols is taken as 1. The diameter of a double-n string is the maximum over all 1 ≤ i < j ≤ n of the distance between i and j. We will call two entries in the list adjacent if their positions in the list differ by no more than the diameter of the string.
Let δ(n) be the minimum diameter over all double-n strings. We can construct a pairwise-intersecting double-interval society from a doublen string with diameter d by assigning intervals of equal width to the symbols, long enough so that each interval overlaps the intervals of the d symbols to its right and left.
For example, consider the double-5 string ABCDEBECAD. This string has diameter 2, since any pair of symbols A through E appear somewhere in this list separated by at most one other symbol (e.g., the second occurrences of A and E in this string are distance 2 apart). We build a society from this string by assigning intervals of equal width as in Figure 2. This society has approval number 3 as can be seen since the right endpoint of A's first interval intersects the left endpoint of C's first interval, and both intersect B's first interval. Hence we see that δ(5) ≤ 2 (and in fact δ(5) = 2). Note that in general the approval number of a society with an underlying double-n string is one more than the diameter, that is, a(S) = d + 1.

Asymptotic approval ratios for double-n string societies
If S is arises from a double-n string with diameter d, then since a(S) = d + 1, we see that the minimal approval ratio of such a society is (δ(n) + 1)/n. By taking limits, we see that n is the asymptotic approval ratio for societies arising from double-n strings. In this section, we will show that 8/23 ≤ ∆ ≤ 5/13.
It is clear that for n > 1 we have δ(n − 1) ≤ δ(n) since for any double-n string we can form a double-(n − 1) string of no larger diameter by deleting both occurrences of the n-th symbol. Given a double-n string S we label the symbols as 1, 2, . . . , n according to the left to right order of their first occurrence within S. It is easy to see that ∆ ≤ 1/2 since the double-n string 1, 2, . . . , n, 1, 2, . . . , n shows that δ(n) ≤ n/2 for n at least 2. In fact, we can show δ(n) < n/2 for n at least 3. Although this does not change the upper bound on ∆, we will need this result for the lower bound 8/23 ≤ ∆.
Suppose n = 4r for some positive integer r. We let S i be the string (i − 1)r + 1, (i − 1)r + 2, . . . , ir of length r and it is easy to check that the diameter of T (n) is 2r − 1 and we have 2r − 1 < n/2. For n = 4r + 1, let S 1 , S 2 , S 3 be as before and let S 4 be the string 3r + 1,. . . ,4r + 1 of length r + 1. Now the diameter of T (n) is 2r, and again we have 2r < n/2 as desired. For n = 4r + 2 we set S 1 and S 4 to have length r and S 2 and S 3 to have length r + 1. Consider b in S i and c in S j with i < j. It is easy to see that unless i = 2 and j = 3, the distance between b and c in T (n) is at most 2r since at least one of S i and S j has length r and the other has length at most r + 1. Moreover, for b in S 2 and c in S 3 the distance between b and c in T (n) is at most r + 1 since both of the substrings S 2 , S 3 and S 3 , S 2 occur in T (n). Thus the diameter of T (n) = 2r and we have 2r < 2r + 1 = n/2. Finally for n = 4r + 3 we set S 1 to have length r and S 2 , S 3 , S 4 to have length r + 1. In this case it is easy to see that the diameter of T (n) is 2r + 1 and we have 2r + 1 < 2r + 3/2 = n/2.
For simplicity, without loss of generality assume that if the first occurrence of symbol m occurs at position i in a double-n string, then all symbols at positions 1 ≤ j < i are less than m (otherwise this condition can be satisfied by a permutation of the symbols in the double-n string). From Lemma 3.1, it is sufficient to consider double-n strings that have diameter less than n/2. It is also easy to obtain the lower bound ∆ ≥ 1/3 as shown in the following lemma.
Proof. Let n = 3r + 1. In any double-n string of diameter d, the first occurrence of the symbol 1 can be adjacent to at most d other symbols while the second occurrence can be adjacent to at most 2d. Because 1 must be adjacent to all n − 1 other symbols, d + 2d ≥ n − 1 = 3r, and so d ≥ r. Proof. Assume that there exists some symbol x both of whose occurrences are within the first n − d entries. Thus the first occurrence of n must be at position at least n + 1, so the distance between x and n is at least d + 1, a contradiction.  Proof. This follows directly from Lemma 3.4 since each of the symbols 1, . . . ,î, . . . , d + 1 occurs within d of the first occurrence of i.
We are now ready to prove the lower bound.
Theorem 3.6. Let r be a positive integer. Then δ(23r) ≥ 8r. Thus the asymptotic approval ratio for double-n strings is bounded below by 8/23.
By Lemma 3.3 the first n − d ≥ 23r − 8r + 1 = 15r + 1 symbols in S are distinct (and in order). Now since d < 8r the first occurrence of the symbol labeled 15r + 1 is not within d of the first occurrence of i for 1 ≤ i ≤ 7r + 1. Thus for any such i we must have the second occurrence of i occurring in one of three sets of positions, namely the block B 1 of length d following the first occurrence of 15r + 1, the block B 2 of length d ahead of the second occurrence of 15r +1, or the block B 3 of length d following the second occurrence of 15r + 1. These blocks are illustrated in Figure 3. Let k j be the number of symbols in 1 ≤ i ≤ 7r + 1 with their second occurrence in block B j . From the preceding observation we have k 1 +k 2 +k 3 ≥ 7r+1 (conceivably such a second occurrence of i could be in both B 1 and B 2 if they overlap).
Note that any pair of symbols in B j lie within d of each other. Suppose without loss of generality that the second occurrence of 1 lies in B 1 . For any i with 1 < i ≤ 7r + 1 with the second occurrence of i in B 1 , both occurrences of i lie within d of an occurrence of 1, since d ≥ 7r. By Corollary 3.5, the number of such i is at most 3d + 1 − n ≤ 3(8r − 1) + 1 − 23r = r − 2, giving k 1 ≤ 1 + r − 2 = r − 1. Let x be the minimal number such that the second occurrence of x is not in B 1 . Then x ≤ r since k 1 ≤ r − 1. Without loss of generality suppose the second occurrence of x is in B 2 . Again, by Corollary 3.5 there are at most Similarly, let y be the smallest symbol (in value) whose second occurrence is in B 3 (i.e., is not in B 1 or B 2 ). There are at most k 1 + k 2 symbols in B 1 ∪ B 2 , so y ≤ 3r − 2. Using Corollary 3.5 one last time, we see that there are at most 3d + (3r − 2) − n ≤ 3(8r − 1) + (3r − 2) − 23r = 4r − 5 symbols i = y with 1 ≤ i ≤ 7r + 1 in B 3 , so k 3 ≤ 4r − 4. However, this is a contradiction: we needed k 1 + k 2 + k 3 ≥ 7r + 1, but Therefore we could not have d < 8r, proving the theorem.
A general argument showing δ(br) ≥ ar, for large r, leads to the inequalities b < 3a and 23a ≤ 8b. Thus the lower bound of Theorem 3.6 is the best possible asymptotic bound using this argument. Now we turn to the upper bound.
Theorem 3.7. For any n > 0, there exists a double-n string with diameter d ≤ 5 n 13 − 1. Hence the asymptotic approval ratio for double-n strings is bounded above by 5/13.
Proof. Note that the double-13 string 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 11, 6, 12, 13, 5, 4, 7, 11, 10, 9, 2, 3, 13, 12, 8 has diameter 4, meaning that any two symbols in it appear somewhere in the double-13 string separated by no more than three other elements. This yields a general construction for double-n strings of any length. Let k = n 13 . Then replacing each symbol i in the above string with the substring k(i − 1) + 1, k(i − 1) + 2, . . . , ki, and removing any symbols in the resulting string that are greater than n, yields a double-n string. An example of this string for n = 34 (k = 3) is shown in Figure 4. Because the diameter of the above double-13 string is 4, any two symbols 1 ≤ i < j ≤ n are within substrings that are separated by at most three substrings of length k. Also, i and j are at worst on the far ends of their substrings, giving a maximum total distance between i and j in the new string of 3 n 13 + 2 n 13 − 1 = 5 n 13 − 1.
(  Figure 4. A double-34 string with diameter ≤ 14 constructed as in Theorem 3.7. Symbols are grouped together by parentheses to elucidate its construction. Some groupings have fewer than three elements since symbols larger than 34 in value are removed. Empty groupings are also omitted.

A double-interval society lower bound
In the previous section we considered double-n strings as examples of societies with low approval ratios. These examples give upper bounds for the minimal guaranteed approval ratio for any society. In this section, we give lower bounds for the minimal guaranteed approval ratio, by considering how general pairwiseintersecting double-interval societies force conditions on the number of intervals that can intersect a given interval at its endpoints. This approach largely ignores the geometry of the approval sets and considers only combinatorial constraints.  Then the approval ratio satisfies Alternatively, the size n of a society achieving a given approval number a(S) is bounded above by ≥ n(n − 1). (4.4) Note that an interval J covers both endpoints of another interval I and contributes 1 to the count B(I) exactly when I is the in the center of J and contributes 1 to the count C(J). This implies: Notice that given an approval number a(S), each interval may have at most a(S) − 1 other sets intersecting its left endpoint. This gives an initial bound and similarly, considering right endpoints: However, if the 2n intervals are ordered by the left endpoint, then the kth interval under this ordering from left to right can have at most k − 1 intervals intersecting its left endpoint, not a(S) − 1. Thus we need to adjust the formulas above, to obtain: Adding these equations and applying equation (4.5) yields So by equation (4.4), we see (4n − a(S))(a(S) − 1) ≥ n(n − 1).
Values of a(S) and the corresponding bounds on n and the approval ratio derived from equation (4.3) are given in Table 1.

Modifying double-n string societies
In this section we give an example of a double-interval society with an approval ratio lower than the bound given by Theorem 3.6, thus showing that double-n strings do not always provide examples of societies with minimal approval ratios. We will require a new notation, called the endpoint representation of a society. We will encode a society as a sequence of symbols (corresponding to the approval sets) representing the order of the endpoints of all the approval sets, each prefixed by a "+" or a "−' to denote a left or right endpoint respectively. For example, the society in Figure 1 is represented as Proposition 5.1. There exists a society of size n = 8 with approval number 3. Hence there exist n for which double-n strings do not produce the lowest possible approval numbers.
The society shown in Figure 5 provides such a society. This example was derived from the double-8 string ABCDEF GHEADF CGBH.
If each interval in the string overlaps two intervals on each side, this arrangement is missing the adjacencies AG, BE, BF , CA, DG, DG and CH and has duplicate adjacencies BC, CD, DC, DE, DF , EG, F G, and GH. By doing a series of moves that interchanges endpoints in such a way as to introduce missing adjacencies (at the expense of duplicate adjacencies) without increasing the approval number, we arrive at the society We note that an example like this with n = 8 and a(S) = 3 cannot be achieved by a double-n string since the first symbol in a double-n string with diameter d is adjacent to at most 3d other symbols. Thus, as in Lemma 3.2, we have n ≤ 3d + 1 = 3(a(S) − 1) + 1, and so the approval number of a double-8 string must be at least 4.
It is not clear how to systematically interchange endpoints to achieve all possible adjacencies. However, an algorithm which aims at making "smart" swaps produced societies with approval ratios given in Table 1. A description of the algorithm can be found in [4]. The results of the hill-climbing algorithm in Figure 6 suggest that the asymptotic approval ratio should be 1/3.

Conclusion and Open Questions
We have studied pairwise-intersecting double-interval societies, and determined bounds for the minimum guaranteed approval ratio for such societies. Such questions naturally motivated the study of double-n strings, which represent certain special double-interval societies with low approval ratios. Although these do not necessarily provide the smallest such ratios, all of the known examples that provide smaller ratios come from modifying the double-n string construction.
There are numerous open questions.
• For double-n strings, is there a systematic way to construct strings of the smallest diameter? Figure 6. Output pairwise-intersection double-interval societies with given sizes and approval ratios found by a heuristic algorithm.
Here AR denotes the approval ratio.
• Beyond double-n strings, is there a better general construction that yields societies with the lowest approval ratios? • With double-n strings, we currently have ∆ bounded by 0.348 ≤ ∆ ≤ 0.385. Can we tighten the bounds on ∆? • What results can be obtained for triple-interval societies?
• What about higher-dimensional approval sets? What can be said if each voter's approval set consists of two convex sets in the plane?
Finally, we end with our initial conjecture, which now has more evidence as support.
Conjecture. For all pairwise-intersecting double-interval societies S, the approval ratio a(S) n ≥ 1 3 .