834 reputation
55
bio website
location
age
visits member for 4 years, 10 months
seen Feb 6 '13 at 5:25

Oct
30
awarded  Yearling
Oct
13
awarded  Nice Answer
Apr
4
awarded  Nice Answer
Feb
5
revised Asking about a quasicommutative semigroup
added 563 characters in body
Feb
5
comment Asking about a quasicommutative semigroup
Perhaps the problem is more basic. I will edit after the light dawns and fills the corners of my cranium. Gerhard "Quantifier Application Is Not Commutative" Paseman, 2013.02.05
Feb
5
comment Asking about a quasicommutative semigroup
OK. I'm in trouble now. Please help. ab= b^ra=a^rb^r =ba since rth powers commute. Or do they? Gerhard "Shouldn't Be Using Martin's Definition?" Paseman, 2013.02.05
Feb
5
comment Asking about a quasicommutative semigroup
I speak hastily, of course. All of the above is for classes of semigroups which share the same r. So I not only assume that r is the same for all a and b (minor quibble, as for a finite semigroup I can take R something like product or max of all r), but also every semigroup in the class uses the same r (not so minor). Gerhard "Now Return To Regular Programming" Paseman, 2013.02.05
Feb
5
comment Asking about a quasicommutative semigroup
After spending two more minutes thinking, I see we can take w to be not only squarefree but of length 1. Thus either I am very confused, or we have that quasicommutative semigroups form a locally finite variety. Gerhard "Has Been Very Confused Before" Paseman, 2013.02.05
Feb
5
answered Asking about a quasicommutative semigroup
Feb
5
comment Mathematical techniques to reduce the amount of storage memory
Quid, his specification is not explicit enough: some of the requirements have to be inferred from the phrase "Big Data". Either n will be large or k will be large or both. In either case, I see it as compressing an array of k binary strings of n bits. For ease of discussion, I assume a skewed distribution of array values, so that the most common entries are stored using d bit codes for each common value, with d much smaller than n. The problem is a common one in CS and industry, with a variety of solutions. Gerhard "Ask Me About System Design" Paseman, 2013.02.05
Feb
5
comment Mathematical techniques to reduce the amount of storage memory
Look up dictionary compression. Especially in the case that k is much greater than 2^n, the idea is to encode common bit vectors by a shorter string that uses fewer than n bits, and use longer strings for combinations that are less rare. This works primarily if the distribution of patterns is far from uniform. For a scheme that works for all possible distributions, bit-vectors are liikely the way to go. Gerhard "Ask Me About Saving Memory" Paseman, 2013.02.05
Feb
5
comment Finding a vertex equidistant from two given vertices in a digraph
Aaron's suggestion makes me think that there is a reduction from the Frobenius coin problem to this one. However, the reduction I am thinking of is exponential; it may be that doing a reduction in the other direction will yield a polynomial time solution (to borrow Aaron's example, polynomial in 6, 10 and 15 and not polynomial in their logs). I don't see such a reduction being more clever than Aaron's adjacency matrix suggestion. Gerhard "Reduce, Recycle, And Reuse Mathematics" Paseman, 2013.02.04
Feb
4
comment Ancient method to study Archimedean spiral
With just a modest amount of being charitable Emil, I see implicit in the question something similar to "What is a weak first-order theory or other logical theory that doesn't need calculus or modern machinery to do what I ask about and that is close to something Archimedes could have used?" . A logical perspective on formal systems that model reasoning in ancient times might help with this and similar questions of interest. Gerhard "That's How I See It" Paseman, 2013.02.04
Feb
4
comment Full-rank linearly independent matrices
Consider the cycle q=(1 2 3 ...n) on the set of columns of an order n matrix over F_2 with n > 1. Let Q=q applied to the order n identity matrix, so the main diagonal is shifted "out of the way". In addition to the n(n-1) matrices I + E_ij for i distinct from j, take also the n matrices Q + E_ii. I think this or a slight modification to resolve parity issues should work as a basis in characteristic 2. Gerhard "Ask Me About System Design" Paseman, 2013.02.03
Feb
3
comment Suggestions for good notation
I can see that being handy when one needs to call out some of the indices. For your example from Bourbaki, I would sooner use X decorated with a hat or overbar to indicate a tuple. Gerhard "That May Just Be Me" Paseman, 2013.02.03
Feb
3
comment Is the empty graph a tree?
I remember attending a MSRI conference in a previous millenium on universal algebra and category theory. I was wondering if a religious battle would break out over the notion of an empty algebra. Fortunately no blood was shed at that conference over the issue. This post reminds me of those years. Tom, I'm afraid I dealt more with nonempty algebras than potentially empty relational structures, so I am not entirely convinced by your comment. Not that you should worry. Gerhard "Pronounces Tom Devoid Of Blame" Paseman, 2013.02.02
Feb
2
comment Choosing a base where a given digit of a given number appears the most times
If you aren't picky, choosing base 1 or some irrational base will likely work. I don't think you should invent a term like "oneier" though. Gerhard "Inventing Words Is Sorta Fun" Paseman, 2013.02.02
Feb
2
comment Which popular games are the most mathematical?
I think my point is that some view games mathematically, for the goal of practicing mathematics. While I understand and often sympathize with such an endeavour, I remind you that some games are for pure social entertainment, and mathematical analysis is often counter to that goal. I would consider a semiotic approach to Charades analysis, and I am not clear what goals your suggested approach are trying to reach. Gerhard "Likes Board Over Party Games" Paseman, 2013.02.01
Feb
1
comment Full-rank linearly independent matrices
If n > 1, any order n matrix is the sum of exactly two invertible matrices, even if the field has characteristic two. So I would expect an invertible basis for characteristic 2 also. Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.01
Feb
1
comment Is the empty graph a tree?
Trees have roots and leaves, and when they are big enough they have branches as well. The one vertex graph is a not big tree, and the empty graph is not a tree, in my view. (The empty graph could be soil, or a dog, or a pink elephant, depending on the metaphor. Unless you need an additive identity though, the empty graph is not a tree.) Gerhard "It Is What You Need" Paseman, 2013.02.01