One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.
Consider now the following variant of the triangle counting problem.
Given is a simple graph $G$ of order $n$ with a weight function defined on the edge set $$w:E(G) \mapsto \mathbb{Z}^{+}.$$ A triangle of $G$ with edges $e_1,e_2,e_3$ is said to be valid if the edge weights are pairwise coprime. That is $$\gcd(w(e_1),w(e_2)) = \gcd(w(e_1),w(e_3)) = \gcd(w(e_2),w(e_3)) = 1.$$
What am I wondering is the following
Can you count the number of valid triangles of a weighted graph $G$ in subcubic time?
Note that if all edge weights are 1 we are dealing with the classical triangle counting problem.
Intuitively I believe that this is not possible since for a fixed vertex $v$ one has to check the gcd for $O(n^2)$ neighbours of $v$ but then again, the matrix multiplication trick is also counter-intuitive in its own way.
So I would like to hear a more refined answer why this cannot be achieved or perhaps how it can be.
