#OK to post homework #Joseph Koutsoutis, 03-03-2024, Assignment 13 read `C13.txt`: #1 #myAllFactors(n,q,x) is intended to output all of the #the factors of x^n-1 mod q (q is a prime) except for 1 and x^n-1. #AllFactors(n,q,x) fails for certain values where x^n-1 has #repeated roots, so this is my attempt to fix this. #For example, x^28-1 mod 2 = (x + 1)^4*(x^3 + x + 1)^4*(x^3 + x^2 + 1)^4, #and myAllFactors(28,2,x) outputs 123 polynomials while #AllFactors(28,2,x) outputs 6 polynomials. myAllFactors := proc(n,q,x) local R,S,s,i,j: R := Sqrfree(x^n-1) mod q: S := map(a -> Berlekamp(a[1], x), R[2]) mod q: S := map(a -> convert(a, list), S): S := [seq([seq(op(S[i]), j in 1..R[2][i][2])], i in 1..nops(S))]: S := ListTools:-Flatten(S): S := {op(powerset(S))} minus {[]}: S := {seq(expand(convert(s,`*`)) mod q,s in S)}: S minus {expand(x^n - 1) mod q}: end: CCshopF:=proc(N,q,x,K,R,W) local n,C,S,M,g,w: C := {}: for n from 2 to N do: S := myAllFactors(n,q,x): for g in S do: M := CtoL(n,x,g): if q^nops(M) <= K and nops(M) / n >= R then: w := MinW(q,M): if w >= W then: C := C union {[g,evalf(nops(M)/n), w]}: fi: fi: od: od: C: end: #Here was my output for CCshopF(30,2,x,10000,1/2,5): # {[x^8 + x^5 + x^4 + x^3 + 1, 0.5294117647, 5], # [x^10 + x^7 + x^6 + x^4 + x^2 + 1, 0.5238095238, 6], # [x^10 + x^8 + x^6 + x^4 + x^3 + 1, 0.5238095238, 6], # [x^8 + x^7 + x^6 + x^4 + x^2 + x + 1, 0.5294117647, 5], # [x^9 + x^8 + x^5 + x^4 + x^2 + x + 1, 0.5714285714, 5], # [x^9 + x^8 + x^7 + x^5 + x^4 + x + 1, 0.5714285714, 5], # [x^11 + x^9 + x^7 + x^6 + x^5 + x + 1, 0.5217391304, 7], # [x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1, 0.5217391304, 7]} #so there were 8 valid polynomials found in my search. #Here was my output for CCshopF(30,3,x,10000,1/2,5): # {[x^5 + 2*x^3 + x^2 + 2*x + 2, 0.5454545455, 5], # [x^5 + x^4 + 2*x^3 + x^2 + 2, 0.5454545455, 5], # [x^6 + 2*x^4 + 2*x^3 + 2*x^2 + 1, 0.5384615385, 5], # [x^6 + x^5 + 2*x^4 + 2*x^2 + x + 1, 0.5384615385, 5], # [x^8 + x^7 + x^5 + 2*x^4 + x^2 + x + 2, 0.5000000000, 5], # [x^8 + 2*x^7 + 2*x^5 + 2*x^4 + x^2 + 2*x + 2, 0.5000000000, 5], # [x^8 + x^7 + 2*x^6 + x^4 + x^3 + x + 2, 0.5000000000, 5], # [x^8 + 2*x^7 + 2*x^6 + x^4 + 2*x^3 + 2*x + 2, 0.5000000000, 5], # [x^8 + x^7 + 2*x^6 + x^4 + x^3 + x^2 + 2*x + 1, 0.5000000000, 5], # [x^8 + 2*x^7 + 2*x^6 + x^4 + 2*x^3 + x^2 + x + 1, 0.5000000000, 5], # [x^8 + x^7 + x^6 + 2*x^5 + x^4 + 2*x^2 + 2*x + 1, 0.5000000000, 5], # [x^8 + 2*x^7 + x^6 + x^5 + x^4 + 2*x^2 + x + 1, 0.5000000000, 5]} #so there were 12 valid polynomials found in my search. #CCshopF(30,5,x,10000,1/2,5) outputted 0 polynomials for me. #2 CtoDual:=proc(n,q,x,g) local i,h,r: h := Quo(x^n-1,g,x) mod q: r := degree(h,x): h := add(coeff(h,x,i)* x^(r-i), i=0..r): CtoL(n,x,h): end: #3 # I forgot some useful determinant properties which give a much nicer proof, # but this was my attempt: # To prove det(V(a,r))=Vd(a,r) I will use a fact from math451 (algebra i) # and I will assume that the entries of this matrix are from the ring F[a_1,...,a_r] # where F is a field and a_1,...,a_r are indeterminates. # We will prove this by induction on r. # If r = 1, this holds trivially so assume r > 1. # Now we want to compute the determinant of: # 1 1 ... 1 # a_1 a_2 ... a_r # (a_1)^2 (a_2)^2 ... (a_r)^2 # . . . . # . . . . # . . . . # (a_1)^{r-1} (a_2)^{r-1} ... (a_r)^{r-1} # Let's first consider computing the determinant in the usual way across the bottom row. # By induction, we have that # det(V(a,r)) = (-1)^{r+1} * (a_1)^{r-1} * prod(a_j - a_i, i < j and i,j != 1) # + (-1)^{r} * (a_2)^{r-1} * prod(a_j - a_i, i < j and i,j != 2) # + ... # + (-1)^{2r} * (a_r)^{r-1} * prod(a_j - a_i, i < j and i,j != r) # We now observe that for any integers x < y, if we set a_x=a_y, we can immediately # remove all terms in det(V(a,r)) that contain a_y - a_x in their # prod(a_j - a_i, i < j and i,j != z) term so that: # det(V(a,r)) = (-1)^{?1} (a_x)^{r-1} prod(a_j - a_i, i < j and i,j != x) # + (-1)^{?2} (a_y)^{r-1} prod(a_j - a_i, i < j and i,j != y) # If the difference between x,y is even, then if we try to compare: # prod(a_j - a_i, i < j and i,j != x) # with # prod(a_j - a_i, i < j and i,j != y) # by using the fact that a_x = a_y, we find that for each z where x < z < y, # there is a term in the first product of the form a_z - a_x and # a corresponding term in the second product of the form a_x - a_z. # Since y-x is even, there is an odd number of such z, so # prod(a_j - a_i, i < j and i,j != x) = -prod(a_j - a_i, i < j and i,j != y) # implying that det(V(a,r)) = 0 since the beginning (-1)^{?} factor will be the same # if y-x is even. Similar analysis handles the case where y-x is odd. # Since we assumed F to be a field, we have that F[a_1,...,a_r] is a UFD. # All (a_y-a_x) are irreducible and therefore prime, so Vd(a,r) | det(V(a,r)). # We now note that our formula above for the det(V(a,r)) tells us that # deg(det(V(a,r))) <= (r-1) + (r-1 choose 2) = (r choose 2) = deg(Vd(a,r)), so # det(V(a,r)) = c * Vd(a,r) where c is an element of F. # From here, we note that by our formula for det(V(a,r)) above, we know that # the term 1*(a_r)^{r-1}(a_{r-1})^{r-2}...(a_2) is present, and there is only one way to obtain # (a_r)^{r-1}(a_{r-1})^{r-2}...(a_2) in Vd(a,r) (by taking a_j from each a_j-a_i), so c=1, # meaning det(V(a,r)) = Vd(a,r). #4 #4.1 # Let Weight(Outcome):=(-1)^NumberOfUpsets*mul(a[i]^s[i],i=1..r). # We first note that Vd(a,r) = prod(a[j] - a[i], i < j) expands to a total of # 2^(r(r-1)/2) terms before simplifying. Each of these terms corresponds to picking # either a[i] or a[j] in all r(r-1)/2 terms (a[j] - a[i]). # We can think of this as corresponding to setting the winner of the game between # player j and player i. # If we treat the index of a as the rank of the player, then choosing a[i] corresponds # to adding an upset, so this term of the expansion of Vd(a,r) is equal # to Weight(the corresponding Outcome). # Since each of the 2^(r(r-1)/2) terms corresponds to a different outcome and there are # 2^(r(r-1)/2) potential outcomes, we conclude that # Vd(a,r)=Sum of all Weight(Outcome) over all possible 2^(r(r-1)/2) outcomes. #4.3 # We first note that if we view this tournament as an orientation of the complete graph K_r, # a transitive outcome must have a directed path of length r (we treat scores as outdegrees here). # This path determines the orientation of all other edges since we need to avoid cycles. # Therefore a transitive tournament must have corresponding score vector that can # be rearranged to obtain [r-1,r-2,...,0]. # It may also be shown that any score vector that can be rearranged to obtain # [r-1,r-2,...,0] corresponds to a transitive tournament. # We now observe that if we have a tournament containing a 3-cycle, # if we change the orientation of each edge in a 3-cycle, # the resulting graph has a score vector that is the same as the previous graph, # but since swapping the orientation of each edge either increases or decreases the # number of upsets by 1, we have Weight(new outcome) = -Weight(old outcome). # With these observations, we'll now prove that the sum of all nontransitive outcomes # is 0. We'll use induction on r, and the case r=1 is trivial so we'll assume r > 1. # For r>1, to show that the sum of all the nontransitive outcomes is 0, we can # use our first observation to focus on all valid score vectors that cannot be rearranged # to obtain [r-1,r-2,...,0]. We will assume by induction that for all nontransitive # outcomes for tournaments with r-1 players, every valid score vector that cannot be # rearranged to obtain [r-2,r-3,...,0] has an even number of associated tournaments, # exactly half of which have an odd number of upsets. # Now let's focus on the r-th player. Given that this player has score s[r], we can # consider all the (r-1 choose s[r]) ways that this player could have obtained this score. # If we fix one of these scenarios, we can decrement the appropriate entries of s[1..r-1] # to obtain the results of only considering the games with the first r-1 players. # Let's call this list of r-1 scores s'. # We may assume without loss of generality that s' corresponds to a valid outcome on r-1 # players. If s' cannot be rearranged to obtain [r-2,r-3,...,0], then we may assume by induction # that there is an even number of associated tournaments on these r-1 players with score vector # s', exactly half of which have an odd number of upsets. Since we fixed the results of # the matches with player r, we fixed the number of upsets in these matches, so combining # these results with all of the smaller tournaments obtained by induction yields an # even number of associated tournaments, exactly half of which have an odd number of upsets. # Now let's assume that s' can be rearranged to obtain [r-2,r-3,...,0]. We know # that in our original score vector s, the values in the first r-1 positions # were all in {0,..,r-1}. We observe that we cannot have had 3 entries all having the # same score in this range since setting the matches with player r can only decrement each # score by at most 1, so s' could not be rearranged to obtain [r-2,r-3,...,0]. # Of the entries where 2 had the same score which we'll call x, similar logic tells # us that if there is a score < x where two players had the same score, there must have # been exactly one score with 0 associated players between x and the largest of the # scores < x with two associated players. # We also observe that at least one score must have appeared twice in s[1..r-1]. # Otherwise, since the sum of the scores is r(r-1)/2, this fixes the score s[r] # so that all scores in {0,...,r-1} would appear exactly once in s, contradicting # our assumption that s could not be rearranged to obtain [r-1,...,0]. # With this, there must be some entries of s[1..r-1] that repeat exactly twice. # In order to obtain s', we are forced to make a choice at these positions and choose # who player r lost to/won against. This gives us all of the ways to obtain # a transitive outcome when only considering the games between the first r-1 players. # We now observe that if we start with fixing some matches involving player r to obtain score s' # and then choose some score that was repeated in s[1..r-1] where we then swap the results of # the match between r and the two players with this score, if we think about the graph obtained, # this corresponds to flipping the 2 edges between player r and these 2 players and also # the edge in between these 2 players. # If we think about the original scenario s', player r must have lost against the player with the lower # score in s' (since they lost a point) and won against the player with the higher score. # We can also show that the player with the higher score in s' must have won against the # player with the lower score since we need to turn s', which can be rearranged into # [r-2,...,0], into a valid tournament. With this perspective, we can see that # swapping the results of the matches between player r and these 2 players corresponds to # swapping the orientation of a 3-cycle. Additionally, since these two players end up with # scores that are only one apart, no other edges are swapped. # By an observation above, this negates the weight of the original outcome, so the # parity of the outcome must have swapped. # Let's say that there are y scores of s[1..r-1] that appear twice. As stated above, # choosing who player r wins against at each of these paired scores gives all # s' that can be rearranged to [r-2,...,0]. If we fix some default result, we can represent # all of these distinct outcomes using y bits, where each bit corresponds to some # score that appears twice in s[1..r-1]. We can say 0 represents that player r # had the same results against the 2 players with the corresponding score as in the default result. # Using the Gray code sequence (https://en.wikipedia.org/wiki/Gray_code), we may # create a sequence of all 2^y combinations of these y bits, where each successive # pair in this sequence differs at exactly one place. This corresponds to swapping the # results of 2 games involving player r which we showed above corresponds # to swapping the parity of the outcome. Therefore exactly half of these tournaments # have an odd number of upsets. # Since we have shown that exactly half of all nontransitive tournaments for any given # score vector have an odd number of upsets, the sum of the weights of all # nontransitive outcomes is 0. #4.2 # By 4.3, the sum of the weights of all nontransitive outcomes is 0, so # Vd(a,r) = sum of weights of all outcomes = sum of weights of all transitive outcomes. #4.4 # I'm going to use induction on r again to prove that det(V(a,r))=Vd(a,r). # Assume r > 1. # We want to compute the determinant of: # 1 1 ... 1 # a_1 a_2 ... a_r # (a_1)^2 (a_2)^2 ... (a_r)^2 # . . . . # . . . . # . . . . # (a_1)^{r-1} (a_2)^{r-1} ... (a_r)^{r-1} # Let's first consider computing the determinant in the usual way across the bottom row. # By induction, we have that # det(V(a,r)) = (-1)^{r+1} * (a_1)^{r-1} * Vd([a_2,a_3,...,a_r],r-1) # + (-1)^{r} * (a_2)^{r-1} * Vd([a_1,a_3,...,a_r],r-1) # + ... # + (-1)^{2r} * (a_r)^{r-1} * Vd([a_1,...,a_{r-1}],r-1) # = (-1)^{r+1} * (a_1)^{r-1} # * (sum of the weights of all transitive tournaments with players a_2,a_3,...,a_r) # + (-1)^{r} * (a_2)^{r-1} # * (sum of the weights of all transitive tournaments with players a_1,a_3,...,a_r) # + ... # + (-1)^{2r} * (a_r)^{r-1} # * (sum of the weights of all transitive tournaments with players a_1,a_2,...,a_{r-1}) # For any transitive transitive tournament with r players, we must have a score vector # that can be rearranged to [r-1,r-2,...,0]. If we say that player a_i has rank i, # then: # Vd(a,r) = sum of the weights of all transitive tournaments # = sum(sum(weights of all transitive tournaments where a_i won r-1 matches), i=1..r) # = sum( # (-1)^{r-i} * (a_i)^{r-1} * (sum of the weights of all transitive tournaments without player a_i), # i=1..r) # = sum( # (-1)^{r+i} * (a_i)^{r-1} * (sum of the weights of all transitive tournaments without player a_i), # i=1..r) # = (-1)^{r+1} * (a_1)^{r-1} # * (sum of the weights of all transitive tournaments with players a_2,a_3,...,a_r) # + (-1)^{r} * (a_2)^{r-1} # * (sum of the weights of all transitive tournaments with players a_1,a_3,...,a_r) # + ... # + (-1)^{2r} * (a_r)^{r-1} # * (sum of the weights of all transitive tournaments with players a_1,a_2,...,a_{r-1}) # = det(V(a,r)) #5 Encode113 := proc(x) local a,b,c,d,eq1,eq2,eq3,eq4,i,S: eq1 := 0 = add(x[i], i=1..6) + a + b + c + d: eq2 := 0 = add(i * x[i], i=1..6) + 7*a + 8*b + 9*c + 10*d: eq3 := 0 = add(i^2 * x[i], i=1..6) + 7^2*a + 8^2*b + 9^2*c + 10^2*d: eq4 := 0 = add(i^3 * x[i], i=1..6) + 7^3*a + 8^3*b + 9^3*c + 10^3*d: S := msolve({eq1,eq2,eq3,eq4}, 11): subs(S, [op(x), a,b,c,d]): end: