# Support Constrained Generator Matrices and the Generalized Hamming Weights

Hao Chen Hao Chen is with the College of Information Science and
Technology/Cyber Security, Jinan University, Guangzhou, Guangdong Province,
510632, China<EMAIL_ADDRESS>The Hao Chen was supported by NSFC Grant
62032009.

###### Abstract

Support constrained generator matrices for linear codes have been found
applications in multiple access networks and weakly secure document exchange.
The necessary and sufficient conditions for the existence of Reed-Solomon
codes with support constrained generator matrices were conjectured by Dau,
Song, Yuen and Hassibi. This conjecture is called the GM-MDS conjecture and
finally proved recently in independent works of Lovett and Yildiz-Hassibi.
From their conjecture support constrained generator matrices for MDS codes are
existent over linear size small fields. In this paper we propose a natural
generalized conjecture for the support constrained matrices based on the
generalized Hamming weights (SCGM-GHW conjecture). The GM-MDS conjecture can
be thought as a very special case of our SCGM-GHW conjecture for linear
$1$-MDS codes. We investigate the support constrained generator matrices for
some linear codes such as $2$-MDS codes, first order Reed-Muller codes,
algebraic-geometric codes from elliptic curves from the view of our SCGM-GHW
conjecture. In particular the direct generalization of the GM-MDS conjecture
about $1$-MDS codes to $2$-MDS codes is not true. For linear $2$-MDS codes
only cardinality-based constraints on subset systems are not sufficient for
the purpose that these subsets are in the zero coordinate position sets of
rows in generator matrices.

##  1 Introduction

For a vector ${\bf a}\in{\bf F}_{q}^{n}$, the Hamming weight $wt({\bf a})$ of
${\bf a}$ is the number of non-zero coordinate positions. The Hamming distance
$d_{1}({\bf a},{\bf b})$ between two vectors ${\bf a}$ and ${\bf b}$ is
defined to be the Hamming weight of ${\bf a}-{\bf b}$. A linear $[n,k]_{q}$
code is a $k$ dimensional subspace ${\bf C}\subset{\bf F}_{q}$. For a linear
code ${\bf C}\subset{\bf F}_{q}^{n}$ of dimension $k$, its Hamming distance
(or weight) $d_{1}$ is the minimum of Hamming distances $d_{1}({\bf a},{\bf
b})$ between any two different codewords ${\bf a}$ and ${\bf b}$ in ${\bf C}$.
It is well-known that the Hamming distance (or weight) of a linear code ${\bf
C}$ is the minimum Hamming weight of non-zero codewords. These codewords of a
linear code ${\bf C}$ with the minimum Hamming weight are called minimum
weight codewords.

The Singleton bound $d_{1}\leq n-k+1$ is the basic upper bound for linear
error-correcting codes. A linear code attaining this bound is called a MDS
(maximal distance separable) code. A long-standing conjecture in the theory of
linear error-correcting codes is the main conjecture for the MDS codes, which
asserts that the length of a linear MDS code over ${\bf F}_{q}$ can not bigger
than $q+1$ except some obvious trivial cases, we refer to [14]. One
achievement is the work [1] of Ball in which the conjecture was proved for
linear MDS codes over prime fields.

Let ${\bf G}$ be a $k\times n$ generator matrix of a linear $[n,k,n-k+1]_{q}$
MDS codes, set ${\bf S}_{i}\subset[n]=\\{1,2,\ldots,n\\}$ be the set of zero
coordinate positions of the $i$-th row of this generator matrix ${\bf G}$.
Then it follows from the MDS condition that for any subset ${\bf
I}\subset[k]=\\{1,2,\ldots,k\\}$, the intersection $\bigcap_{i\in I}{\bf
S}_{i}$ has at most $k-|I|$ elements. The GM-MDS conjecture claims that for
given $n$ and $k$, and any given subset system ${\bf S}_{1},\ldots,{\bf
S}_{k}$ of $[n]$ satisfying the MDS condition

$|I|+|\bigcap_{i\in I}{\bf S}_{i}|\leq k,$

if

$q\geq n+k-1,$

then there is a $k\times n$ generator matrix ${\bf G}$ of a linear
$[n,k,n-k+1]_{q}$ MDS code over ${\bf F}_{q}$ such that ${\bf S}_{i}$ is in
the set of zero coordinate positions of the $i$-th row of ${\bf G}$ for
$i=1,2,\ldots,k$.

The above conjecture was proposed by Dau, Song, Yuen, Hassibi in [3, 9] from
the motivation of multiple access network coding scheme. It was found its
application in weakly secure document exchange in [22]. There have been a lot
of progress in [4, 10, 11, 12, 18] since this conjecture was formulated in [3]
and this GM-MDS conjecture was finally proved in two independent papers [23,
15]. In [7] further results about smaller field with size $n$ was proved under
stronger conditions on the set systems. In [26] Gabidulin codes with support
constrained generator matrices were constructed. For other development and
related conjectures we refer to [25, 16, 15, 8]. In particular it was
conjectured that for general support constraints generator matrices can only
be existent over exponential size fields in [15]. This kind general problem is
about random codes and thus theoretically significant. Our generalized SCGM-
GHW conjecture is more concentrated on the practically significant well-known
structured linear codes.

It is natural to consider the following problem. For a well-constructed linear
code over ${\bf F}_{q}$, what support set conditions should be imposed for
generator matrices? Can a sparse generator matrix with support constraints
satisfying the above support set conditions be explicitly given? This problem
is a far more generalization of the GM-MDS conjecture and thus have
applications in multiple access network coding scheme. On the other hand
sparse generator matrices are helpful for highly efficient encoding for linear
codes over general finite fields. Theoretically this is also a combinatorial
problem for the structures of linear codes.

The generalized Hamming weights of linear codes in [21] are naturally related
to the support constrained matrices. The support of a linear sub-code
$D\subset{\bf C}$ is

$\operatorname{supp}(D)=\\{1\leq i\leq n:x_{i}\neq 0:\exists
x=(x_{1},\ldots,x_{n})\in D\\},$

that is, the support of a linear sub-code $D$ is the non-zero coordinate
positions of all codewords in $D$. The $r$-th generalized Hamming weight
$d_{r}$ for $1\leq r\leq k$ is defined to be the minimum of the number of
support positions of arbitrary $r$ dimension sub-codes. Hence $d_{1}$ is the
minimum Hamming weight. It is clear that $d_{1}<d_{2}<\cdots<d_{k}$ and the
generalized Singleton bound $d_{r}\leq n-k+r$ is satisfied for a linear
$[n,k]_{q}$ code. Moreover the $r$-th generalized Hamming weight of a linear
$[n,k]_{q}$ MDS code is exactly $n-k+r$ for $1\leq r\leq k$. We refer to [21]
for the other properties of the generalized Hamming weights. The weight
hierarchy or generalized Hamming weights of many well-constructed linear
codes, such as cyclic codes, Hermitian codes, $q$-ary Reed-Muller codes have
been determined in [5, 6, 17].

A linear $[n,k]_{q}$ code over ${\bf F}_{q}$ is called $r$-MDS for some $r$ in
the range $1\leq r\leq k$, if $d_{r}=n-k+r$. Then it is also $s$-MDS for any
$s\geq r$, see [20]. The linear MDS codes are then $1$-MDS. Hence $r$-MDS
codes for $r\geq 2$ are natural generalizations of linear MDS codes. A well-
known result in weight hierarchy or higher weights about algebraic-geometric
codes due to Tsfasman and Vlǎdut is that these codes are $g+1$-MDS if they are
from genus $g$ curves, see [20] Corollary4.2. As algebraic-geometric codes
from genus $0$ curves, the Reed-Solomon codes are MDS ($1$-MDS). The next
interesting cases are these algebraic-geometric codes from elliptic curves,
that is, genus $1$ curves. They are $2$-MDS codes.

Let ${\bf F}_{q}$ be an arbitrary finite field, $P_{1},\ldots,P_{n}$ be $n\leq
q$ elements in ${\bf F}_{q}$. The Reed-Solomon codes $RS(n,k)$ is defined by

$RS(n,k)=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf F}_{q}[x],\deg(f)\leq k-1\\}.$

This is a $[n,k,n-k+1]_{q}$ linear MDS code, since a degree $\deg(f)\leq k-1$
polynomial has at most $k-1$ roots. From the interpolation it is clear that
for any given $k-1$ distinct points among $P_{1},\ldots,P_{n}$ there is one
nonzero polynomial $f$ of degree

$\deg(f)\leq k-1$

such that $f$ is zero at these $k-1$ points. That is, every subset of
$\\{P_{1},\ldots,P_{n}\\}$ with cardinality $k-1$ is the the set of zero
coordinate positions of at least one nonzero codeword.

The Reed-Solomon codes can be generalized to algebraic-geometric codes as
follows. Let ${\bf X}$ be an absolutely irreducible non-singular genus $g$
curve defined over ${\bf F}_{q}$. Let ${\bf P}=\\{P_{1},\ldots,P_{n}\\}$ be a
set $n$ distinct rational points of ${\bf X}$ over ${\bf F}_{q}$. Let ${\bf
G}$ be a rational divisor over ${\bf F}_{q}$ of degree $\deg({\bf G})$
satisfying $2g-2<\deg({\bf G})<n$ and

$support({\bf G})\bigcap{\bf P}=\emptyset.$

Let ${\bf L}({\bf G})$ be the associated function space. The algebraic-
geometric codes associated with ${\bf G}$, $P_{1},\ldots,P_{n}$ is defined by

${\bf C}({\bf P},{\bf G},{\bf X})=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf
L}({\bf G})\\}.$

From the Riemann-Roch Theorem the dimension of this code is

$k=\deg({\bf G})-g+1.$

The minimum Hamming distance is

$d_{1}\geq n-\deg({\bf G}).$

The Reed-Solomon codes are just the algebraic-geometric codes over the genus
$0$ curve. As in the case of the Reed-Solomon codes, from the Riemann-Roch
Theorem any subset of $\\{P_{1},\ldots,P_{n}\\}$ of cardinality $\deg({\bf
G})-g$ is in the set of zero coordinate positions of at least one nonzero
codeword.

One achievement of the theory of algebraic-geometric codes is the sequence of
algebraic-geometric codes over ${\bf F}_{q^{2}}$ satisfying

$R+\delta\geq 1-\frac{1}{q-1},$

which is exceeding the Gilbert-Varshamov bound. We refer to [19] for the
detail.

The $q$-ary Reed-Muller codes are defined as follows. Let $P_{1},\ldots,P_{n}$
be $n=q^{m}$ points of ${\bf F}_{q}^{m}$. Let $u\leq m$ be a positive integer.
Set ${\bf Function}(u,m)$ be the set of linear combinations of monomials
$x_{i_{1}}^{j_{1}}x_{i_{2}}^{j_{2}}\cdots x_{i_{t}}^{j_{t}}$, where $j_{i}\leq
q-1$ for $i=1,\ldots,t$,$t\leq u$. The $u$ order Reed-Muller code $RM(u,m)$ is
defined by

$RM(u,m)=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf Function}(u,m)\\}.$

We consider the first order $q$-ary Reed-Muller code $RM(1,m)$. The dimension
is

$k=1+m,$

and the minimum distance is

$d_{1}=(q-1)q^{m-1}.$

##  2 The SCGM-GHW conjecture

We prove the following result, from which the MDS condition in the GM-MDS
conjecture is a very special case.

Theorem 2.1. Let ${\bf C}$ be a linear $[n,k]_{q}$ code over the finite field
${\bf F}_{q}$ with the generalized Hamming weights $d_{1}<d_{2}<\cdots<d_{k}$.
Let ${\bf G}$ be a size $k\times n$ generator matrix of this code ${\bf C}$.
Set ${\bf S}_{i}$, $i=1,2,\ldots,k$, the set of zero coordinate positions of
the $i$-th row of this generator matrix ${\bf G}$. Then we have

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|}$

for any subset $I\subset[k].$

Proof. For any subset of size $I$ in the set $[k]=\\{1,2,\ldots,k\\}$, the
$|I|$ corresponding rows of ${\bf G}$ generate a $|I|$ dimensional sub-code of
${\bf C}$, hence we have

$d_{|I|}\leq n-|\bigcap_{i\in I}{\bf S}_{i}|.$

The conclusion follows immediately.

For a linear $[n,k]_{q}$ MDS code, we have $d_{r}=n-k+r$. Then we have
$|I|+|\bigcap_{i\in I}{\bf S}_{i}|\leq k$. This is the MDS condition on the
set systems in the GM-MDS conjecture. Hence the GM-MDS conjecture due to Dau,
Song, Yuen and Hassibi in [3, 9] can be reformulated as the following
conjecture.

The GM-MDS conjecture based on the GHW. If the subset system ${\bf
S}_{1},\ldots,{\bf S}_{k}$ in $[n]$ satisfies the generalized Hamming weight
based constraints for a linear $[n,k]_{q}$ MDS code,

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|},$

where $d_{1},\ldots,d_{k}$ are the generalized Hamming weights of a linear
$[n,k]_{q}$ MDS code, if $q\geq n+k-1$, there is a linear $[n,k]_{q}$ MDS code
with a support constrained generator matrix ${\bf G}$ such that the set ${\bf
S}_{i}$ is in the set of zero coordinate positions of the $i$-th row of ${\bf
G}$ for $i=1,2,\ldots,k$.

A generalized MDS condition for the MDS condition in the GM-MDS conjecture was
proposed in [15] and studied in [7]. Our reformulation of the MDS condition
based on the generalized Hamming weights in the GM-MDS conjecture is for
linear codes and motivated from the existence of support constrained generator
matrices.

The direct generalization conjecture is as follows. Let ${\bf C}$ be a linear
$[n,k]_{q}$ code over the finite field ${\bf F}_{q}$ with the generalized
Hamming weights $d_{1}<d_{2}<\cdots<d_{k}$. Let ${\bf S}_{1},\ldots,{\bf
S}_{k}$ be a subset system in $[n]$ satisfying

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|}.$

Is there a corresponding support constrained generator matrix ${\bf G}$ such
that for $i=1,2,\ldots,k$, the set ${\bf S}_{i}$ is in the set of zero
coordinate positions of the $i$-th row of ${\bf G}$?

This is clearly false because for some special constructed linear codes, there
are not sufficiently many minimum weight codewords. For an arbitrary linear
$[n,k]_{q}$ code, and any given subset ${\bf S}\subset[n]$ with the
cardinality smaller than or equal to $k-1$, there exists a nonzero codeword
such that this set ${\bf S}$ is in the set of zero coordinate positions of
this codeword, hence we propose the following version as a far more
generalization of the GM-MDS conjecture.

The SCGM-GHW Conjecture. Let ${\bf C}$ be a linear $[n,k]_{q}$ code over the
finite field ${\bf F}_{q}$ with the generalized Hamming weights
$d_{1}<d_{2}<\cdots<d_{k}$. Let ${\bf S}_{1},\ldots,{\bf S}_{k}$ be a subset
system in $[n]$ with their cardinalities smaller than or equal to $k-1$. If
this subset system satisfies the following GHW-based constraints

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|},$

then there is a support constrained generator matrix generator matrix ${\bf
G}$ such that for $i=1,2,\ldots,k$, the set ${\bf S}_{i}$ is in the set of
zero coordinate positions of the $i$-th row of ${\bf G}$.

When the generalized Hamming weights are from the linear $[n,k]_{q}$ MDS code,
the above conjecture degenerates to the very special case, that is, the GM-MDS
conjecture. The beautiful result of Lovett and Yildiz-Hassibi can be restated
as following result.

Dau-Song-Yuen-Lovett-Yildiz-Hassibi Theorem ([15, 23, 24]) The above
conjecture is true for linear $[n,k]_{q}$ MDS codes over ${\bf F}_{q}$
provided $q\geq n+k-1$.

In [7] the smaller field size results are proved if some further stronger
restraints on the subset systems are imposed.

There are two aspects about our SCGM-GHW conjecture, one aspect is about a
class of linear codes such as $1$-MDS codes in the GM-MDS conjecture. Since
the GM-MDS conjecture are about $1$-MDS linear codes, we can consider the
conjecture about $2$-MDS linear codes. The generalized Hamming weights of
$2$-MDS linear codes are as follows,

$d_{1}=n-k,$ $d_{2}=n-k+2,$ $\cdots,$ $d_{r}=n-k+r,$ $\cdots,$ $d_{k}=n.$

Hence the GHW -based support constrained conditions on the subset systems for
two or more subsets are the same as the MDS condition in the GM-MDS
conjecture. The case of one subset constraint $|{\bf S}_{i}|\leq k-1$ is
stronger than the condistion

$|{\bf S}_{i}|\leq n-d_{1}=k.$

GM-$2$-MDS conjecture. . Let ${\bf S}_{1},\ldots,{\bf S}_{k}$ be a subset
system in $[n]$ with their cardinalities smaller than or equal to $k-1$. If
this subset system satisfies the constraints

$|\bigcap_{i\in I}{\bf S}_{i}|+|I|\leq k$

for any subset $I\subset[k]$ with $|I|\geq 2$. Over sufficiently large field
${\bf F}_{q}$ we have a linear $[n,k,n-k]_{q}$ $2$-MDS code and a support
constrained generator matrix ${\bf G}$ such that for $i=1,2,\ldots,k$, the set
${\bf S}_{i}$ is in the set of zero coordinate positions of the $i$-th row of
${\bf G}$.

We will show that the above conjecture is not true even for arbitrary large
finite fields. That is, only cardinality-based constraints on the subset
systems are not sufficient for the purpose that these subsets are in the zero
coordinate position sets of rows in a generator matrix. There are deeper
cardinality-independent restraints on the configurations of these subsets.

The second aspect of our SCGW-GHW conjecture is totally code-depending. That
is, the conjecture is only considered for the generalized Hamming weights for
one concrete code, not a class of codes. The natural generalization of the
Reed-Solomon codes are algebraic-geometric codes. Hence the possible
generalizations of the above excellent result of Dau-Song-Yuen-Lovett-Yildeiz-
Hassibi for algebraic-geometric codes are particularly fascinating. Notice
that actually there are many different curves even when the genus of the
curves is fixed. The possible generalizations of the GM-MDS conjecture to
algebraic-geometric codes are interesting combinatorial problems about their
codeword support configurations.

Many algebraic-geometric $[n,k]_{q}$ codes from elliptic curves with code
lenght $n>q+2$ have their generalized Hamming weights as above. However for
algebraic-geometric code from elliptic curve cases, not every subset of $[n]$
of the cardinality $k$ can be the set of zero coordinate positions of nonzero
codeword, we refer to the Section 3. The condition $|{\bf S}_{i}|\leq k-1$ is
a natural constraint. Then our SCGM-GHW conjecture for algebraic-geometric
codes from elliptic curves is as follows.

The SCGM-GHW Conjecture for AG-codes from elliptic curves. Let ${\bf C}$ be a
linear $[n,k,n-k]_{q}$ algebraic-geometric code from an elliptic curve defined
over the finite field ${\bf F}_{q}$. Their generalized Hamming weights are
$d_{1}=n-k$, $d_{r}=n-k+r$ for $r=2,\ldots,k$. Let ${\bf S}_{1},\ldots,{\bf
S}_{k}$ be a subset system in $[n]$ with their cardinalities smaller than or
equal to $k-1$. If this subset system satisfies the GHW-based constraints

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|},$

then there is a support constrained generator matrix generator matrix ${\bf
G}$ such that for $i=1,2,\ldots,k$, the set ${\bf S}_{i}$ is in the set of
zero coordinate positions of the $i$-th row of ${\bf G}$.

We will show that the above conjecture is not true as in the case of $2$-MDS
codes. Further cardinality-independent constraints on the subset systems are
need such that these subsets are in the set of zero coordinate positions of
rows of a generator matrix.

Then the following version of SCGM-GHW conjecture seems plausible. It is
totally code-dependent. From the following Proposition 2.1 it is not true for
general linear codes. However it seems that this conjecture could be true for
many linear codes. Notice that the condition 1) is satisfied automatically for
any subset of cardinality $k-1$ for linear $[n,k,n-k+1]_{q}$ MDS codes, thus
the following conjecture is a natural generalization of the GM-MDS conjecture
for subsets with the cardinality $k-1$.

The code-dependent version of SCGM-GHW conjecture. Let ${\bf C}$ be a linear
$[n,k]_{q}$ code over the finite field ${\bf F}_{q}$ with the generalized
Hamming weights $d_{1}<d_{2}<\cdots<d_{k}$. Let ${\bf S}_{1},\ldots,{\bf
S}_{k}$ be a subset system in $[n]$ satisfying the following two conditions.
1) $|{\bf S}_{i}|=n-d_{1}$ and for each ${\bf S}_{i}$ there is a nonzero
codeword of weight $d_{1}$ such that ${\bf S}_{i}$ is its set of zero
coordinate positions,
1) This subset system satisfies the GHW-based constraints

$|\bigcap_{i\in I}{\bf S}_{i}|\leq n-d_{|I|}.$

Then there is a support constrained generator matrix generator matrix ${\bf
G}$ such that for $i=1,2,\ldots,k$, the set ${\bf S}_{i}$ is in the set of
zero coordinate positions of the $i$-th row of ${\bf G}$.

We will prove that this conjecture is true for the first order $q$-ary Reed-
Muller codes and some dimension $3$ algebraic-geometric codes from elliptic
curves over an arbitrary finite field. Hence it seems for elliptic curve cases
the field size is not the key point of the existence of support constrained
generator matrices. This is quite different when compared with the GM-MDS
conjecture.

It is obvious that the codes satisfying the above code-version SCGM-GHW
conjecture are spanned by their minimum weight codewords.

Proposition 2.1. If the above code-depending SCGM-GHW conjecture is true for a
linear code ${\bf C}$. Then this code is spanned by minimum weight codewords.

##  3 Support constrained generator matrices for the algebraic-geometric codes
from the elliptic curves

Let ${\bf C}$ be the elliptic curve over ${\bf F}_{4}$ defined by
$y^{3}=x^{2}+x$ over ${\bf F}_{4}$. Let $\omega$ be the element in ${\bf
F}_{4}$ such that $\omega^{2}+\omega+1=0$. Then the $8$ rational points of the
above elliptic curve is of the form
$P_{1}=(0,0),P_{2}=(1,0),P_{3}=(\omega,1),P_{4}=(\omega,\omega),P_{5}=(\omega,\omega^{2}),P_{6}=(\omega^{2},1),P_{7}=(\omega^{2},\omega),P_{8}=(\omega^{2},\omega^{2})$.
We have a dimension $3$ algebraic-geometric $[8,3,5]_{4}$ code from this
elliptic curve with the following generator matrix. The 2nd and 3rd
generalized Hamming weights are $d_{2}=7$ and $d_{3}=8$.

$\left(\begin{array}[]{cccccccc}1&1&1&1&1&1&1&1\\\
0&1&\omega&\omega&\omega&\omega^{2}&\omega^{2}&\omega^{2}\\\
0&0&1&\omega&\omega^{2}&1&\omega&\omega^{2}\\\ \end{array}\right)$

Set ${\bf S}_{1}=\\{P_{4},P_{8}\\}$, ${\bf S}_{2}=\\{P_{3},P_{7}\\}$ and ${\bf
S}_{3}=\\{P_{5},P_{6}\\}$. Then every set has $k-1=2$ elements. Moreover this
subset system satisfies the GHW-based constraint in our SCGM-GHW conjecture
for AG-codes from elliptic curves. For $i=1,2,3$, the functions of the form
$a_{0}+a_{1}x+a_{2}y$, $a_{i}\in{\bf F}_{4}$, for $i=1,2,3$, which are zero at
the two points in ${\bf S}_{i}$ have to be the form $a(x+\omega^{i-1}y)$ for
an arbitrary nonzero element $a\in{\bf F}_{4}$. Hence these functions are zero
at the point $P_{1}$. It is clear that the three functions of the above form
is linearly dependent. Hence there is no $3\times 8$ generator matrix ${\bf
G}$ of this algebraic-geometric code such that ${\bf S}_{1},{\bf S}_{2},{\bf
S}_{3}$ are in the zero coordinate position sets of rows in ${\bf G}$. This is
a counter-example for the SCGM-GHW conjecture for AG-codes from elliptic
curves.

This linear $[8,3,5]_{4}$ code is also $2$-MDS. The three sets ${\bf
S}_{1},{\bf S}_{2},{\bf S}_{3}$ satisfy the GHW-constraints in our GM-$2$-MDS
conjecture. This is also a counter-example for the GM-$2$-MDS conjecture.

The above counter-example can be generalized to arbitrary elliptic curve
cases.

Proposition 3.1. Let ${\bf E}$ be an elliptic curve defined over ${\bf
F}_{q}$. Let ${\bf P}=\\{P_{1},\ldots,P_{n}\\}$ be a set $n$ distinct rational
points of ${\bf E}$. Let ${\bf G}$ be a rational divisor over ${\bf F}_{q}$ of
degree $k=\deg({\bf G})$ satisfying $0<\deg({\bf G})<n$ and

$support({\bf G})\bigcap{\bf P}=\emptyset.$

Let ${\bf Q}$ be a fixed point in the set ${\bf P}$. Assume that the minimum
Hamming weight of the code ${\bf C}({\bf P},{\bf G},{\bf E})$ is $d_{1}=n-k$.
Suppose there are $k$ subsets

${\bf S}_{i}=\\{P_{1}^{i},\ldots,P_{k-1}^{i}\\},$

for $i=1,2,\ldots,k$, of ${\bf P}$ with the cardinality $k-1$ such that there
exists functions in ${\bf L}({\bf G})$ which are zero at points,
$P_{1}^{i},\ldots,P_{k-1}^{i},Q$ for each ${\bf S}_{i}$. Then there is no
generator matrix ${\bf G}$ of the algebraic-geometric code ${\bf C}({\bf
P},{\bf G},{\bf E})$ such that ${\bf S}_{i}$ is in the set of zero coordinate
position set of the $i$-th row of ${\bf G}$ for $i=1,2,\ldots,k$.

Proof. For each $i\in[k]$, from the Riemann-Roch Theorem the dimension of the
linear subspace of functions in ${\bf L}({\bf G})$ which are zero at the
points in ${\bf S}_{i}$ is one. All these functions are zero at the point $Q$.
The conclusion follows directly.

Since all algebraic-geometric codes from elliptic curves are $2$-MDS, the
above result gives many counter-examples for the GM-$2$-MDS conjecture.

On the other hand the code-depending version of SCGM-GHW conjecture is true
for some algebraic-geometric codes from elliptic curves. Let $P^{2}({\bf
F}_{q})$ be the projective plane over the finite field ${\bf F}_{q}$, ${\bf
E}\subset{\bf P}^{2}({\bf F}_{q})$ be an absolutely non-singular degree $3$
curve. Then the genus of this curve is $\frac{(3-2)(3-1)}{2}=1$ and ${\bf E}$
is an elliptic curve. Let ${\bf G}$ be a degree $3$ rational divisor defined
by a line $a_{0}x_{0}+a_{1}x_{1}+a_{2}x_{2}=0$, where $x_{0},x_{1},x_{2}$ are
homogeneous coordinates of ${\bf P}^{2}({\bf F}_{q})$,
$a_{0},a_{1},a_{2}\in{\bf F}_{2}$. Let ${\bf P}$ be a set of $n$ rational
points of ${\bf E}$. We assume $support({\bf G})\bigcap{\bf P}=\emptyset$.
Then ${\bf C}({\bf P},{\bf G},{\bf E})$ is a dimension $3$ algebraic-geometric
code from ${\bf E}$. Assume that there are three points $P_{1},P_{2},P_{3}$ in
${\bf P}$ which are on one line, then the minimum Hamming weight of this code
is $n-3$. Hence this is a linear $[n,3,n-3]_{q}$ code which is also $2$-MDS.

Proposition 3.2. The code-depending version of SCGM-GHW conjecture is true for
above $3$-dimensional algebraic-geometric codes ${\bf C}({\bf P},{\bf G},{\bf
E})$ from degree $3$ plane curves.

Proof. Since the functions in ${\bf L}({\bf G})$ are of the form

$\frac{b_{0}x_{0}+b_{1}x_{1}+b_{2}x_{2}}{a_{0}x_{0}+a_{1}x_{1}+a_{2}x_{2}},$

where $b_{0},b_{1},b_{2}\in{\bf F}_{q}$. Then from the condition 1 in the
code-depending version of SCGM-GHW conjecture the subset ${\bf
S}_{i}\subset{\bf P}$, $i=1,2,3$, is consisting of three points in ${\bf P}$
which are on one projective line. Then condition ${\bf S}_{i}\bigcap{\bf
S}_{j}$ has at most one point. Thus the GHW-based constraints for $|I|=2$ is
satisfied automatically. The condition ${\bf S}_{1}\bigcap{\bf
S}_{2}\bigcap{\bf S}_{3}$ is empty implies that there is no one point in the
three projective lines corresponding to ${\bf S}_{1},{\bf S}_{2},{\bf S}_{3}$.
Hence these three projective lines are linearly independent. The conclusion
follows directly.

##  4 Support constrained generator matrix for the first order $q$-ary Reed-
Muller code

The main result in this Section is the following result, which asserts that
the SCGM-GHW conjecture is not true, and the coding-dependent version of SCGW-
GHW conjecture is true for the first order $q$-ary Reed-Muller codes. The
generalized Hamming weights of the first order $q$-ary Reed-Muller code
$RM(1,m)$ are as follows, see [13],

$d_{1}=(q-1)q^{m-1},$ $d_{2}=q^{m}-q^{m-2},$ $d_{r}=q^{m}-q^{m-r},$
$d_{m}=q^{m}-1,$

and

$d_{m+1}=q^{m}.$

Proposition 4.1. The SCGM-GHW conjecture is not true and the code-depending
SCGM-GHW conjecture is true for the first order $q$-ary Reed-Muller codes.

Proof. In the code-depending version of our SCGM-GHW conjecture case, each
${\bf S}_{i}$ is the zero subspace of an affine function of the form

$a_{0}+a_{1}x_{1}+\cdots+a_{m}x_{m},$

where $a_{i}\in{\bf F}_{q}$ for $i=0,1,\ldots,m$. Hence there are exactly
$q^{m-1}$ points in ${\bf S}_{i}$ for $i=1,2,\ldots,m+1$. From the GHW-based
constraints

$|\bigcap_{i\in I}{\bf S}_{i}|\leq q^{m}-d_{|I|},$

$|I|$ such affine spaces intersect at a dimension $m-|I|$ affine subspace,
when $|I|\leq m$, and intersect at the empty set when $|I|=m+1$. Hence we can
find exactly $m+1$ linearly independent affine functions such ${\bf S}_{i}$,
$i=1,2,\ldots,m+1$ is exactly the set of zero coordinate positions of the
$i$-th affine function.

In the SCGM-GHW conjecture case each ${\bf S}_{i}$ has at most $m$ points and
we can find three subsets ${\bf S}_{1},{\bf S}_{2},{\bf S}_{3}$ consisting of
$m$ points in general positions, such that for each ${\bf S}_{i}$, there is
only one dimensional subspace

${\bf A}_{i}=\\{f:f(s)=0,s\in{\bf S}_{i}\\},$

in the linear span of $1,x_{1},\ldots,x_{m}$. We require that the intersection
of these three subsets is a set of $m-1$ points in general positions. Hence
${\bf A}_{1},{\bf A}_{2},{\bf A}_{3}$ are not linearly independent. It is easy
to extend these three subsets to $1+m$ subsets satisfying the GHW constraints

$|\bigcap_{i\in I}{\bf S}_{i}|\leq q^{m}-d_{|I|}.$

The conclusion follows directly.

In the code-depending version of SCGW-GHW if we only require that each subset
${\bf S}_{i}$ is contained in the set of a non-zero codeword, the conjecture
is not true again. For Reed-Muller codes, since the supports of their
codewords have to be linear, only cardinality-dependent constraints are not
sufficient for the existence of support constraint generator matrices.

##  5 Conclusion

The GM-MDS conjecture then theorem is a beautiful result about the support
configurations of codewords in generator matrices of linear $1$-MDS codes. We
show that the MDS condition in the GM-MDS conjecture is a special case of a
more generalized constraint based on the generalized Hamming weights for
general linear codes. Then we propose a support constraint generator matrix
conjecture based on the above GHW-based constraints. This is a natural
generalization of the GM-MDS conjecture. From the view of this SCGM-GHW
conjecture the support constrained generator matrices of the first order
$q$-ary Reed-Muller code, algebraic-geometric codes from elliptic curves are
studied. In particular the direct generalization of the GM-MDS conjecture
about $1$-MDS codes to $2$-MDS codes is not true. Not like the GM-MDS
conjecture for $1$-MDS code case, the field size seems not the key point of
the existence of support constrained generator matrices in the $2$-MDS linear
code case. It would be interesting to investigate if our SCGM-GHW conjecture
is true for general various algebraic-geometric codes.

## References

  * [1] S. Ball, On large subsets of a finite vector space in which every subset of basis size is a basis, Jornal of Eurpean Mathematical Society, Vol. 14, pp. 733-748, 2012.
  * [2] Hao Chen, Support constrained generator matrices for algebraic-geometric codes, In preparation, 2021.
  * [3] S. H. Dau, W. Song, and C. Yuen, On the existence of MDS codes over small fields with constrained generator matrices, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 1787-1791, 2014.
  * [4] S. H. Dau, W. Song and C. Yuen, On simple multiple access networks, IEEE Journal on Selected Areas on Communications, Vol. 33, pp. 236-249, 2015.
  * [5] G. van der Geer and M. van der Vlugt, On generalized weights of BCH codes, IEEE Transactions on Information Theory, Vol. 40, pp. 543-546, 1994.
  * [6] G. van der Geer and M. van der Vlugt, Generalized Hamming weights of BCH(3) revisited, IEEE Transactions on Information Theory, Vol. 41, pp. 300-301, 1995.
  * [7] G. Greaves and J. Syatriadi, Reed-Solomon codes over small fields with constrained generator matrices, IEEE Transactions on Information Theory, Vol. 65, pp. 4764-4770, 2019.
  * [8] S. Gopi, V. Guruswami and S. Yekhanin, Maximally recoverable LRCs, A field size lower bound and constructions for few heavy parties, IEEE Transactions on Information Theory, Vol. 66, pp. 6066-6083, 2020.
  * [9] W. Halbawi, T. Ho, H. Yao and I. Duursma, Distributed Reed-Solomon codes for simple multiple access networks, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 651-655, 2014.
  * [10] W. Halbawi, Z. Liu and B. Hassibi, Balanced Reed-Solomon codes, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 935-939, 2016.
  * [11] W. Halbawi, Z. Liu and B. Hassibi, Balanced Reed-Solomon codes for all parameters, Proc. IEEE Inf. Theory Workshop, pp. 409-413, 2016.
  * [12] A. Heidarzadeh and A. Sprintson, An algebraic-combinatorial proof technique for the GM-MDS conjecture, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 11-15, 2017.
  * [13] P. Heijnen and R. Pellikaan, Generalized Hamming weights of $q$-ary Reed-Muller codes, IEEE Transactions on Information Theory, Vol. 44, pp. 181-196, 1998.
  * [14] J. H. van Lint, Introduction to the coding theory, GTM 86, Springer, 1982.
  * [15] S. Lovett, MDS matrices over small fields: A proof of the GM-MDS conjecture, Proc. IEEE 59th Annual Symposium on Foundation of Computer Science FOCS, pp. 194-199, 2018.
  * [16] D. Kane, S. Lovett and S. Rao, The independence number of the birkhoff polytope graph, and applications to maximally recoverable codes, Proc. IEEE 58th Annual Symposium on Foundation of Computer Science, FOCS, 2017\.
  * [17] C. Munuera and D. Ramirez, The second and third generalized Hamming weights of Hermitian codes, IEEE Transactions on Information Theory, Vol. 45, pp. 709-712, 1999.
  * [18] W. Song and K. Cai, Generalized Reed-Solomon codes with sparsest and balanced generator matrices, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 1-5, 2018.
  * [19] M. Tsfasman and S. G. Vlǎdut, Algebraic-geometric codes, Vol.58, Springer Science and Business Media, 2013.
  * [20] M. Tsfasman and S. G. Vlǎdut, Geometric approach to higher weights, IEEE Transactions on Information Theory, Vol. 41, pp. 1564-1588, 1995.
  * [21] V. K. Wei, Generalized Hamming weights of linear codes, IEEE Transactions on Information Theory, Vol. 37, pp. 1412-1413, 1991.
  * [22] M. Yan, A. Sprintson, and I. Zelenko, Weakly secure data exchange with Generalized Reed-Solomon codes, Proc. IEEE Int. Symp. Inf. Theory, ISIT, pp. 1366-1370, 2014.
  * [23] H. Yildiz and B. Hassibi, Optimum linear codes with support constraints over small fields, Proc. IEEE Inf. Theory Workshop, pp. 1-5, 2018.
  * [24] H. Yildiz and B. Hassibi, Optimum linear codes with support constraints over small fields, IEEE Transactions on Information Theory, Vol. 65, pp. 7868-7874, 2019.
  * [25] H. Yildiz and B. Hassibi, Further progress on the GM-MDS conjecture for Reed-Solomon codes, Proc. IEEE Int. Symp. Inf. Theory, ISIT, 2018.
  * [26] H. Yildiz and B. Hassibi, Gabidulin codes with support constrained generator matrices, IEEE Transactions on Information Theory, Vol. 66, pp. 3638-3649, 2020


This preprint comprises the first four out of five chapters of the Master's thesis I wrote 2022 under the supervision of Catharina Stroppel and Paul Wedrich at the University of Bonn titled "Categorified Jones–Wenzl projectors and Generalizations". It can serve as introductory literature for researchers or graduate students familiar with Schur–Weyl duality between the symmetric group and the general linear Lie algebra or their quantum counter parts, and who are seeking to learn a type $B$/$D$ analogue of the famous type $A$ story. Chapter 1 serves as an introduction to the type $B$ combinatorics and blob-diagrammatics. Chapters 2,3, and 4 contain proofs of three main theorem each - the first one is an explicit/computational proof of the easiest case of quantum coideal Schur–Weyl duality involving non-trivial quantizations of weight spaces, the second one shows the generalization of Jones–Wenzl projectors to the type $B$ Temperley–Lieb algebra and the third one uses  generalized Reidemeister moves and a functional analytic argument to prove a version of the fact that powers of the type $D$ full-twist converge towards the type $D$ Jones–Wenzl projector.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleBull. Lond. Math. Soc.
titleCompletions of Grothendieck groups

journaltitleGeom. Topol.
titleKhovanov's homology for tangles and cobordisms

Springer-Verlag, Berlin

noteTranslated from the 1968 French original by Andrew Pressley
seriesElements of Mathematics (Berlin)
titleLie groups and Lie algebras. Chapters 4–6

Springer, New York

titleFunctional analysis, Sobolev spaces and partial differential equations

journaltitleActa Arith.
titleA $p$-adic Perron-Frobenius theorem

Princeton University Press

seriesMathematical Notes
titleThe Classical and Quantum $6j$-symbols

Mathematical Sciences Publishers

journaltitleAlgebraic & Geometric Topology
titleAn exceptional collection for Khovanov homology

journaltitleQuantum Topology
titleCategorification of the Jones-Wenzl Projectors

journaltitleRepresent. Theory
titleDeligne's category $\underline{Rep}(GL_\delta)$ and representations of general linear supergroups

journaltitleArch. Math.
titleTemperley-Lieb algebras associated to the root system $D$

journaltitleJournal of Algebra
titleRepresentations of Hecke algebras of type $B_n$

titleCategorical diagonalization of full twists

journaltitleSel. Math. New Ser.
titleDiagrammatic description for the categories of perverse sheaves on isotropic Grassmannians

journaltitleAdv. Math.
titleNazarov–Wenzl algebras, coideal subalgebras and categorified skew Howe duality

Springer-Verlag New York

seriesGraduate Texts in Mathematics
subtitleA First Course
titleRepresentation Theory

journaltitleQuantum Topol.
titleCategorifying fractional Euler characteristics, Jones–Wenzl projectors and $3j$-symbols

journaltitleAnn. Math. Blaise Pascal
titleBasic results on braid groups

The Clarendon Press, Oxford University Press, New York

seriesLondon Mathematical Society Monographs. New Series
titleCharacters of finite Coxeter groups and Iwahori–Hecke algebras

World Scientific

journaltitleJournal of Knot Theory and its Ramifications
titleGeneralized Temperley–Lieb algebras and decorated tangles

journaltitleJ. Lie Theory
titleWeyl groups with Coxeter presentation and presentation by conjugation

Springer-Verlag New York

seriesGraduate Texts in Mathematics
titleIntroduction to Lie Algebras and Representation Theory

Cambridge University Press

seriesCambridge Studies in Advanced Mathematics
titleReflection groups and Coxeter groups

titleSchur-Weyl duality for certain infinite dimensional ${U}_q(\mathfrak{sl}_2)$-modules
Representation Theory (math.RT),FOS: Mathematics,FOS: Mathematics,17B37,20G42 (primary) 81R50 (secondary)

Addison-Wesley Publishing Co., Reading, Mass.

noteWith a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson
seriesEncyclopedia of Mathematics and its Applications
titleThe representation theory of the symmetric group

Springer-Verlag New York

seriesGraduate Texts in Mathematics
titleQuantum Groups

ProQuest LLC, Ann Arbor, MI

noteThesis (Ph.D.)–Louisiana State University and Agricultural & Mechanical College
titleA polynomial invariant of links in a solid torus

Princeton University Press

seriesAnnals of Mathematics Studies
titleTemperley-Lieb Recoupling Theory and Invariants of $3$-Manifolds

journaltitleProc. Lond. Math. Soc. (3)
titleBraided module categories via quantum symmetric pairs

Springer, New York

noteWith the graphical assistance of Olivier Dodane
seriesGraduate Texts in Mathematics
titleBraid groups

University of Warwick

titleA study of braids in 3-manifolds

Singapore: World Scientific

booktitleProceedings of the conference on quantum topology, Manhattan, KS, USA, March 24–28, 1993
titleSolid torus links and Hecke algebras of \({\mathcal B}\)-type

journaltitleJ. Knot Theory Ramifications
titleKnot theory related to generalized and cyclotomic Hecke algebras of type $B$

Cambridge Univ. Press, Cambridge

booktitleNew directions in Hopf algebras
seriesMath. Sci. Res. Inst. Publ.
titleCoideal subalgebras and quantum symmetric pairs

journaltitleMathematische Annalen
titleThree-manifolds and the Temperley-Lieb algebra

titleAnnular webs and Levi subalgebras
Quantum Algebra (math.QA),Geometric Topology (math.GT),Representation Theory (math.RT),FOS: Mathematics,FOS: Mathematics,Primary: 17B37 Secondary: 18M15,20C08

journaltitleJ. Eur. Math. Soc. (JEMS)
titleThe Brauer category and invariant theory

journaltitleJ. Algebraic Combin.
title$G(\ell,k,d)$-modules via groupoids

journaltitleLett. Math. Phys.
titleThe blob algebra and the periodic Temperley-Lieb algebra

noteSequence A000712
titleThe On-Line Encyclopedia of Integer Sequences

journaltitleModern Phys. Lett. A
titleOn representations of cyclotomic Hecke algebras

journaltitleTransform. Groups
titleModule categories, weak Hopf algebras and modular invariants

journaltitleJ. Algebra
titleSpecht modules and symmetric groups

Aix-Marseille Université

titleShuffle analogues for complex reflection groups G(m, 1, n)

journaltitleMath. Res. Lett.
titleExtremal weight projectors

journaltitleFund. Math.
titleAn infinite torus braid yields a categorified Jones–Wenzl projector

Springer-Verlag, New York-Heidelberg

noteTranslated from the second French edition by Leonard L. Scott
seriesGraduate Texts in Mathematics, Vol. 42
titleLinear representations of finite groups

journaltitleMath. Proc. R. Ir. Acad.
titleA spectral theoretic proof of Perron-Frobenius

journaltitleJ. Algebra
titleClassical weight modules over $\imath$quantum groups

University of Bonn

titleIdempotente und Jones–Wenzl Projektoren


# Generative AI for Product Design: Getting the Right Design and the Design
Right

Matthew K. Hong, Shabnam Hakimi, Yan-Ying Chen, Heishiro Toyoda, Charlene Wu,
Matt Klenk  matt.hong, shabnam.hakimi, yan-ying.chen, heishiro.toyoda,
charlene.wu<EMAIL_ADDRESS>Toyota Research Institute4440 El Camino
RealLos AltosCAUSA94022

(2023)

###### Abstract.

Generative AI (GenAI) models excel in their ability to recognize patterns in
existing data and generate new and unexpected content. Recent advances have
motivated applications of GenAI tools (e.g., Stable Diffusion, ChatGPT) to
professional practice across industries, including product design. While these
generative capabilities may seem enticing on the surface, certain barriers
limit their practical application for real-world use in industry settings. In
this position paper, we articulate and situate these barriers within two
phases of the product design process, namely getting the right design and
getting the design right, and propose a research agenda to stimulate
discussions around opportunities for realizing the full potential of GenAI
tools in product design.

generative ai, large language models, product design

††copyright: acmcopyright††journalyear: 2023††conference: Make sure to enter
the correct conference title from your rights confirmation emai; April 23–28,
2023; Hamburg, Germany††booktitle: CHI ’23: ACM CHI Conference on Human
Factors in Computing Systems, April 23–28, 2023, Hamburg, Germany††ccs:
Applied computing Media arts††ccs: Human-centered computing Interaction
paradigms

##  1\. Introduction

The publication of the seminal paper, “Attention is all you need”, by Vaswani
et al. (Vaswani et al., 2017) in 2017 marked an important milestone111Recent
advances in generative AI are often attributed to Vaswani et al.’s paper,
which describes a simple self-attention based Transformer architecture that
significantly increases the quality of language models while reducing model
training time. in AI research, fueling an arms race toward the development of
large scale language models (LLM’s). The emergence of LLM’s represent an
inflection point in model performance where they begin to outperform humans in
many benchmark tasks, including speech and image recognition, language
understanding, among others(Sevilla et al., 2022; Wei et al., 2022).

These advances in LLM’s provide the backbone for Generative AI (GenAI) models
and recent explosion of creativity support tools(Insights, 2023) that present
promising opportunities to augment human creativity in real-world professional
practice. Brands such as Nike and Heinz and creative ad agencies already use
text-to-image GenAI tools to create product placement advertisements(Bonilla,
2022). Furthermore, an artwork created with Midjourney won Colorado State
Fair’s fine art competition, stirring debate over its legitimacy(Roose, 2022).
While exciting, it is unknown at this point if these tools are improving human
performance, if so, in what ways, and what interfaces and interactions will
best support professionals.

Designing digital and physical products is a labor-intensive endeavor. At its
core is an iterative process of idea elaboration and reduction, where each
step adds significant cognitive, psychological, and physical burden for the
designer. Innovative design practitioners emphasize the importance of getting
the right design prior to getting the design right and then investing in
implementing fully functional systems(Buxton, 2010). The separation of these
two approaches allows the designer to prioritize finding the global maxima
first instead of optimizing too early and settling for suboptimal solutions.
In theory, GenAI may address this problem by reducing the burden of
elaboration and by enticing the designer in new directions at a low cost. In
either case, working with GenAI models is significantly different from
industrial design practice and therefore, significant support will be
required.

In this position paper, we contribute a discussion around HCI challenges to
applying GenAI in each of these phases. In getting the right design, we
identify a potential tradeoff between inspiration and the efficiency at
generating high-fidelity designs along with challenges in the current
interaction modalities of these tools and designer expectations. In getting
the design right, we identify a human-centered challenge of achieving common
ground with the GenAI model and a technical challenge of how different models
of consumer preference should influence the process.

##  2\. Getting the Right Design

Design is a wicked problem which has no single definitive solution—there is
only constant tension between elaboration of a possible solution and
generating new solutions in another part of the design space. Combating such
uncertainty in design requires a thorough investigation of the design space by
enumerating meaningfully distinct choices of ideas, and adding elaborations to
these ideas to identify the global maxima. By design, the generative
capabilities of GenAI should support designers in accelerating their
exploration of the design space, yet there are important considerations that
challenge their use for professional practice.

###  2.1. High-fidelity design or inspiration?

The ease of which GenAI tools generate photorealistic images, while efficient,
also creates new problems for design. Moving to high-fidelity so quickly could
actually have a negative impact on designer creativity. For example, showing a
high-fidelity solution so early in the process may induce _design fixation_
(Youmans and Arciszewski, 2014), the process in which designers continue to
offer variations on an existing design without considering alternative
solutions. The HCI and design disciplines have emphasized the gradual
evolution of designs from low to high fidelity with evaluation interspersed
throughout iterative steps in the design cycle. The additional time spent
moving from low-fidelity to high-fidelity may result in important learnings
that may lead to creative breakthroughs.

This makes the compelling case to treat GenAI as tools for inspiration,
instead of outright design, in this early stage of the design process. For
instance, many product designers draw inspiration from community-driven visual
content curation websites such as Pinterest and Behance, in order to generate
mood boards that help steer their creative process. However, because these
websites are optimized to attract user engagement, the displayed content may
prematurely constrain the boundaries from which designers draw their
inspiration. GenAI can fill this gap by providing computational means of
generating alternative sources of inspiration(Sbai et al., 2018)

###  2.2. Increasing idea diversity

While many generative AI tools and services already focus on providing
augmentations and variations of human-created visual content, they often
create variations on visual style than the ideas presented in the image.
Navigating the design space requires out-of-the-box thinking, which comes from
the process of elaborating on ‘meaningfully distinct’ ideas. These ideas,
however, are susceptible to, and often influenced by the designers’ own
intuition, experience and biases about the topic.

To this end, future development of GenAI tools should consider computational
means for increasing idea diversity by offering ideas that are visually and
semantically distinct from each other, and create appropriate mechanisms for
users to control the desired level of diversity to prevent significant
deviations from each idea. Idea diversity can also come from systematic
explorations of existing designs across product categories(Hope et al., 2022)
and domains(Kang et al., 2022). To make GenAI tools useful for product design,
we should explore opportunities to integrate our knowledge of conceptual
mappings in natural language–that are sensitive to different social and
cultural contexts–as well as human-made products that embody some knowledge of
the problem and design space.

###  2.3. Prompt engineering challenge

Text-to-image translation systems offer designers the ability to translate
envisioned concepts into photo-realistic design artifacts in just a matter of
seconds. However, adopting prompt engineering-based design in business
practice is challenging because of the cognitively difficult task of
translating designers’ visual concepts into text expressions. This translation
involves clearly articulating intended meanings and remembering specific
design ontology (e.g., surrealism, extreme close-up shot) that is recognized
by the generative model. This problem leads to text prompts that result in
image depictions that are inconsistent with the designer’s intended visual
concept, or vice versa, thus adding significant time to iteratively refine the
prompt until the desired outcome is achieved(Hutchinson et al., 2022). In one
example, using DALL-E 2’s GenAI system, it took Nestlé more than 1,000 text
prompts, followed by human evaluation of each, to arrive at its final product
placement advertisement for its yogurt product by re-rendering Johannes
Vermeer’s painting “The Milkmaid”(Bonilla, 2022).

By interactively prompting users to specify and correct these details (either
through language or imagery), GenAI systems can aid the user in iteratively
improving the scene in fewer input-output loops. Only then can designers begin
to consider adding variations while retaining control over specific design
elements.

##  3\. Getting the Design Right

While the responsibility of getting the right design falls mostly on the
designer, getting the design right requires a concerted effort among design,
engineering, marketing, and other invested stakeholders. Once a design problem
is defined, the product team must make continuous iterative refinements to an
idea to narrow down the design space. Doing so requires making decisions on
concepts to align with the goals set forth by the product team. These goals
are informed by the team’s analysis of engineering requirements, rigorous
usability testing, and measuring consumer reactions to the product, etc. Here,
we focus on capturing consumer preferences, a challenging prospect that adds
significant cost burden and uncertainty in getting the design right.

###  3.1. Maintaining design goals

As a company brings a new product to market, it will learn that there may be
trade-offs between different functional requirements. For example, consumers
may want a sturdy artifact that is also light and inexpensive. Throughout the
product development cycle, engineers will make decisions that navigate these
trade-offs typically without strong links to the information used in the
requirements engineering process. Providing this information to decision-
makers in their workflow has the potential to significantly improve the
resulting design while reducing lead time to bring new products to market. An
important challenge here is how to represent the consumer’s desires begin as
under-specified requirements for later refinement and communication.

Consumers do not care solely about the functional capabilities of the product.
Aesthetic considerations drive many purchase decisions. As the design moves
from concept to production, many engineering decisions will impact the
aesthetic of the resulting artifact. By maintaining the designer’s views of
the consumer’s preferences, these engineering changes can be evaluated for
their aesthetic impacts without consulting expensive design panels. The larger
challenge exists in representing the tension between functional and aesthetic
requirements and teaching GenAI models to generate results that consider the
combination of these constraints.

###  3.2. Multi-modal representations of consumer preference

Predicting how the public will respond to new products is a central problem
for all firms. Vast consumer preference data are expressed and captured in the
form of unstructured text as well as behavioral, and physiological signals.
Data are analyzed in service of creating bespoke personas that represent
consumer preferences, including the target customers’ goals, demographic and
socioeconomic background, lifestyle, values, etc. These personas play an
important role in the design process, particularly to help ground the design
in the context of data. Text-to-text GenAI tools such as ChatGPT or other LLM-
based variants can provide early capabilities to generate personas that embody
recent trends in consumer preferences and even play the role of the persona by
responding to users’ natural language queries.

While there is merit in harnessing textual representations of consumer
preference, there is inherent risk in treating LLM-based personas as proxy for
a target demographic. We don’t fully understand whose opinions are reflected
in the generated responses, and there is potential for representational
harms—there is either too much or a lack of representation from demographic
subgroups(Santurkar et al., 2023).

We believe there is potential in considering other types of data, including
behavioral and physiological signals. There is huge risk in not knowing how
consumers will behave in the presence of the designed product and if there are
certain underlying physiological signals that help predict their preference
toward functional or aesthetic features of a product, especially since
preferences over such features may be outside of a consumer’s conscious
awareness.

For GenAI to be useful in grounding the process of getting the design right,
we call for a greater need for the broader HCI community to invest in efforts
to generate behavioral(Barthet et al., 2022) as well as physiologically-based
personas. For instance, the emerging field of neurodesign applies research
findings from psychology and applied neurosciences to understand how people
respond to various kinds of design and visual stimuli(Auernhammer et al.,
2021). Cross-disciplinary efforts in this direction may yield fruitful
outcomes for grounding product design.

###  3.3. Shifting preferences with time

The most frustrating aspect of industrial product design is that consumer
preferences shift across demographics and time. Once we have consumer
preference models underlying the functional and aesthetic requirements, it is
necessary to understand that products are not designed for the average
consumer. Instead, designers use personas and market segments to target their
products. During design, the target market segments may be refined, additional
segments may be considered, or new consumer preferences may be identified. By
linking consumer preferences to functional and aesthetic considerations, we
should be able to update them dynamically based on new information.

This requirement, however, challenges our use of frozen LLM’s, which limits
the designer’s ability to learn new trends in the market. Retraining LLM’s
incurs significant costs, financially and environmentally, and may present
practical barriers to consider their use for understanding quick changes in
consumer preferences. One practical use of text-to-text GenAI tools is to
understanding slow-changing trends while using complementary methods to
understand emerging trends at the time when newly designed products will be
introduced to the market.

##  4\. Conclusion

We conclude this paper by bringing awareness to the legal and ethical risks
that accompany the use of GenAI tools as they are trained on billions of
intellectual property without giving proper credit to the original creators.
Significant efforts are also needed in addressing the lack of diversity and
inclusion in datasets used to train GenAI models. While we do not discuss
these problems in this paper, we do believe that responsible use of GenAI will
ease potential strain in our society as well as empower product design teams.

## References

  * (1)
  * Auernhammer et al. (2021) Jan Auernhammer, Neeraj Sonalkar, and Manish Saggar. 2021\.  NeuroDesign: From neuroscience research to design thinking practice.  _Design thinking research: Interrogating the doing_ (2021), 347–355.
  * Barthet et al. (2022) Matthew Barthet, Ahmed Khalifa, Antonios Liapis, and Georgios Yannakakis. 2022.  Generative personas that behave and experience like humans. In _Proceedings of the 17th International Conference on the Foundations of Digital Games_. 1–10.
  * Bonilla (2022) Brian Bonilla. 2022\.  How ad agencies are using AI image generators—and how they could be used in the future.  https://adage.com/article/agency-news/how-agencies-use-ai-image-generators-dalle-e-2-midjourney-and-stable-diffusion/2430126.  Accessed: 2023-2-20.
  * Buxton (2010) Bill Buxton. 2010\.  _Sketching user experiences: getting the design right and the right design_.  Morgan kaufmann.
  * Hope et al. (2022) Tom Hope, Ronen Tamari, Daniel Hershcovich, Hyeonsu B Kang, Joel Chan, Aniket Kittur, and Dafna Shahaf. 2022.  Scaling Creative Inspiration with Fine-Grained Functional Aspects of Ideas. In _Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems_. 1–15.
  * Hutchinson et al. (2022) Ben Hutchinson, Jason Baldridge, and Vinodkumar Prabhakaran. 2022\.  Underspecification in Scene Description-to-Depiction Tasks.  _arXiv preprint arXiv:2210.05815_ (2022).
  * Insights (2023) C B Insights. 2023\.  The generative AI landscape: Top startups, venture capital firms, and more.  https://www.cbinsights.com/research/generative-ai-funding-top-startups-investors/.  Accessed: 2023-2-19.
  * Kang et al. (2022) Hyeonsu B Kang, Sheshera Mysore, Kevin Huang, Haw-Shiuan Chang, Thorben Prein, Andrew McCallum, Aniket Kittur, and Elsa Olivetti. 2022\.  Augmenting Scientific Creativity with Retrieval across Knowledge Domains.  _arXiv preprint arXiv:2206.01328_ (2022).
  * Roose (2022) Kevin Roose. 2022\.  An A.I.-Generated Picture Won an Art Prize. Artists Aren’t Happy.  _The New York Times_ (Sept. 2022).
  * Santurkar et al. (2023) Shibani Santurkar, Esin Durmus, Faisal Ladhak, Cinoo Lee, Percy Liang, and Tatsunori Hashimoto. 2023\.  Whose Opinions Do Language Models Reflect?  _arXiv preprint arXiv:2303.17548_ (2023).
  * Sbai et al. (2018) Othman Sbai, Mohamed Elhoseiny, Antoine Bordes, Y LeCun, and C Couprie. 2018.  Design inspiration from generative networks.  _Cornell University_ (2018).
  * Sevilla et al. (2022) Jaime Sevilla, Lennart Heim, Anson Ho, Tamay Besiroglu, Marius Hobbhahn, and Pablo Villalobos. 2022\.  Compute trends across three eras of machine learning. In _2022 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–8.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022\.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ (2022).
  * Youmans and Arciszewski (2014) Robert J Youmans and Thomaz Arciszewski. 2014.  Design fixation: Classifications and modern methods of prevention.  _AI EDAM_ 28, 2 (2014), 129–137.