function sketchpad
global m n A B K K1 phi ksig ptil bet
m=2
n=3

while 1
  K = genK(m,n);  K1 = getK1(K,m,n); ksig = (K>0)';
  
  if 0
    s=0;
    for y=1:m
      ky=getky(K,y,m,n);
      s = s + pl(sum(ky)) + Psi(ky,m,n-1);
    end
    tryfail(abs(s-Psi(K,m,n)),1e-9,'not equal');
    continue
  end
  
  
  if flip
    %if 0
    randliphi
  else
    optphi
  end
  %advphi
  
  [A,B,LB,UB] = alfab(K,m,n);
  UB1 = UB+1;
  [x,fval] = linprog(-K,A,B,[],[],LB,UB1);
  bet = x';
  
  tryfail(-fval,pl(sum(K))+Psi(K1,m,n-1),'bad sublip poly');
  
  ptil = pl(phi-ksig);
  if ~all(A*ptil' < B+1e-9)
    'bad ptil'
    keyboard
  end
  
  %works
  %kapalf
  %alfconj

end
return


function [fval,alf] = alflp(K,m,n)
global ptil
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

A=zeros(0,mn);
B=zeros(0,1);
rind = 0;
rind = 0;
for ind1 = 1:mn
  for ind2 = ind1+1:mn
    x = ind2coord(ind1,MN);
    y = ind2coord(ind2,MN);
    if rho(x,y)==1  % Hamming dist == 1
      if (sign(K(ind1))==sign(K(ind2)))
        % signs equal -- ordinary Lip. cond
        if 1 % seems to matter
          for s = [-1,1]
            rind = rind+1;
            A(rind,ind1) =  s;
            A(rind,ind2) = -s;
            B(rind,1) = 1;
          end
        end
      else
        % try w/o this? -- not quite
        % try alternative
        % "neg" ind - "pos" ind <= 2
        % "pos" - "neg" <= 0
        if (K(ind1)>0)
          pos = ind1;
          neg = ind2;
        else
          pos = ind2;
          neg = ind1;
        end
        rind = rind+1;
        A(rind,neg) = -1;
        A(rind,pos) =  1;
        B(rind,1) = 0;
        % seems to be sufficient...
        if 0
          rind = rind+1;
          A(rind,neg) =  1;
          A(rind,pos) = -1;
          B(rind,1) = 2;
          rind = rind+1;
          A(rind,neg) = -1;
          A(rind,pos) =  1;
          B(rind,1) = 0;
        end
      end
    end
  end
end

LB = 0*K;
UB = LB + n - (~~pl(K));

[x,fval] = linprog(-K,A,B,[],[],LB,UB);
alf = x';
fval = -fval;

lhs = max(A*ptil' - B) ;
rhs = 0;
tryfail(lhs,rhs,'ptil glitch');
return


function [fval,alf] = alflp1(K,m,n)
global ptil
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

A=zeros(0,mn);
B=zeros(0,1);
rind = 0;
for xind=1:mn1
  for x1 = 1:m
    y = ind2coord(xind,MN1);
    xy = [x1 y];
    zind1 = coord2ind(xy,MN);
    if K(zind1) > 0
      rind = rind+1;
      A(rind,zind1) = 1;
      B(rind,1) = n1;
    end
    for y1 = 1:m
      xy = [y1 y];
      zind2 = coord2ind(xy,MN);
      if ((K(zind1) < 0) & (K(zind2) > 0))
        rind = rind+1;
        A(rind,zind1) = -1;
        A(rind,zind2) = +1;
        B(rind,1) = 0;
      end
      
      if (sign(K(zind1))==sign(K(zind2)))
        z1 = ind2coord(zind1,MN);
        z2 = ind2coord(zind2,MN);
        if rho(z1,z2)==1  % Hamming dist == 1
          for s=[-1,+1]
            rind = rind+1;
            A(rind,zind1) =  s;
            A(rind,zind2) = -s;
            B(rind,1) = 1;
          end
        end
      end
    end
  end
end

[x,fval] = linprog(-K,A,B,[],[],0*K,n+0*K);  
alf = x';
fval = -fval;

lhs = max(A*ptil' - B) ;
rhs = 0;
tryfail(lhs,rhs,'ptil glitch');
return


function [fval,alf] = alflp0(K,m,n)
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

A=zeros(0,mn);
B=zeros(0,1);
rind = 0;
for xind=1:mn
  if K(xind) > 0
    rind = rind+1;
    A(rind,xind) = 1;
    B(rind,1) = n1;
  end
  for yind=1:mn
    if ((K(xind) < 0) & (K(yind) > 0))
      rind = rind+1;
      A(rind,xind) = -1;
      A(rind,yind) = +1;
      B(rind,1) = 0;
    end
  end
end

[x,fval] = linprog(-K,A,B,[],[],0*K,n+0*K);  
alf = x';
fval = -fval;
return


function randliphi
global m n A B K K1 phi ksig ptil
phi = randlip(m,n);
ptil = pl(phi-ksig);
return

function advphi
global m n A B K K1 phi ksig ptil
% adversarial phi
phi = zeros(1,m^n);    
ii = find(K>0);    
phi(ii) = n*ones(size(ii));  
ptil = pl(phi-ksig);
return

function optphi
global m n A B K K1 phi ksig ptil
[A,B] = lipab(m,n); 
[x,fval] = linprog(-K,A,B,[],[],0*K,n+0*K);  
phi = round(x'); 
ptil = pl(phi-ksig);
return

function alfconj0
global m n A B K K1 phi ksig ptil
%[fval,alf] = alflp(K,m,n);
lhs = fval;
rhs = Psi(K1,m,n-1);
%rhs = sum(pl(K1)); % nope, seem to need the full Psi
tryfail(lhs,rhs,'alfconj FALSE');

lhs = alf*K;
rhs = pl(sum(K1)) + sumky(K1,m,n-1);
tryfail(lhs,rhs,'huh?');

if 1
  %a1 = alf-1;
  %a1 = alf - ksig;
  a1 = min(alf,n-1);
  %tryfail(alf*K,sum(K)+a1*K,'oppa');
  %tryfail(alf*K,pl(sum(K))+a1*K,'oppanki'); % true but don't care
  tryfail(alf*K,pl(sum(K))+pl(a1)*K,'oppachki');
  %tryfail(alf*K,sum(K)+pl(a1)*K,'oppusinki'); % not this one!!
  %tryfail(a1*K,pl(a1)*K,'oppusinki');
end
  
if 0
  s=0;
  for y=1:m
    ky=getky(K,y,m,n);
    ay=getky(alf,y,m,n);
    ay = pl(ay-1);
    s = s + pl(sum(ky)) + ay*ky;
    %s = s + sum(ky) + ay*ky;
  end
  lhs = alf*K;
  rhs = s;
  tryfail(lhs,rhs,'nuuuuuuuuuu');
  %tryfail(abs(lhs-rhs),1e-9,'nuuuuuuuuuu');
end

return

function kapalf
global m n A B K K1 phi ksig ptil
for y=0:(m-1)
  if 0
    lhs = 0;
    rhs = 0;
    for x=0:(m-1)
      %lhs = alf([0 0])*kap([0 0]) + alf([1 0])*kap([1 0]);
      %rhs = pl(kap([0 0]) + kap([1 0]));
      %tryfail(lhs,rhs,'kapalf1');
      lhs = lhs + alf([x y])*kap([x y]);
      rhs = rhs + kap([x y]);
    end
    rhs = pl(rhs);
  end
  ky=getky(K,y+1,m,n);
  ay=getky(ptil,y+1,m,n);
  lhs = ay*ky;
  rhs = pl(sum(ky));
  tryfail(lhs,rhs,['kapalf1 y=' num2str(y+1)]);

  [fval,alf] = alflp(ky,m,n-1);
  lhs = fval;
  rhs = pl(sum(ky));
  tryfail(lhs,rhs,['kapalf2 y=' num2str(y+1)]);
end
return

function k = kap(x)
global m n A B K K1 phi ksig ptil
k = akval(x,K);
return

function a = alf(x)
global m n A B K K1 phi ksig ptil
a = akval(x,ptil);
return

function ak = akval(x,AK)
global m n
MN  = repmat([m],[1 n ]);
x = x+1;
i = coord2ind(x,MN);
ak = AK(i);
return

function b = works
global m n A B K K1 phi ksig ptil

lhs = phi*K;
rhs = Psi(K,m,n);
tryfail(lhs,rhs,'major failure');

lhs = ptil*K;
rhs = Psi(K1,m,n-1);
tryfail(lhs,rhs,'minor failure, still bad');


%lhs1 = abs(phi*K - sumkphiy(K,phi,m,n));
%rhs1 = 1e-9;
%tryfail(lhs1,rhs1,'idiot');

if 0
  lhs = phi*K;
  %rhs = sumkphiy(K,phi,m,n);
  rhs = pl(sum(K)) + sumky(K,m,n);
  tryfail(lhs,rhs,'nope1');
  % NO, FAILS
end

if 0
  lhs = ptil*K;
  rhs = sumky(K1,m,n-1);
  tryfail(lhs,rhs,'nope2');
  % THIS FAILS TOO
end
return

for y=1:m
  Ky = getky(K,y,m,n);
  phiy = getky(phi,y,m,n);
  
  ii = find(phiy==n); phiy(ii) = phiy(ii)-1;
  
  lhs2 = phiy*Ky;
  rhs2 = Psi(Ky,m,n-1);
  tryfail(lhs2,rhs2,'next step');

  rhs1 = rhs1 + phiy*Ky;
  
  % here is our massage:
end
tryfail(lhs1,rhs1,'first step fails');
return


function b = works5
global m n A B K K1 phi

lhs1 = phi*K;
rhs1 = pl(sum(K));
for y=1:m
  Ky = getky(K,y,m,n);
  phiy = getky(phi,y,m,n);
  
  ii = find(phiy==n); phiy(ii) = phiy(ii)-1;
  
  lhs2 = phiy*Ky;
  rhs2 = Psi(Ky,m,n-1);
  tryfail(lhs2,rhs2,'next step');

  rhs1 = rhs1 + phiy*Ky;
  
  % here is our massage:
end
tryfail(lhs1,rhs1,'first step fails');
return



function sketchpad11
global m n A B K K1 phi
m=3
n=3

while 1
  K = genK(m,n);  K1 = getK1(K,m,n); ksig = (K>0)';
  
  if 0
    % THIS IS FALSE
    lhs = sumky(K,m,n);
    rhs = Psi(K1,m,n-1);
    good = (lhs <= rhs+1e-9)
    if ~good
      'dont work'
      keyboard
    end
  end
  
  if 1
    
    %if flip
    if 0
      phi = randlip(m,n);
    else
      [A,B] = lipab(m,n);      [x,fval] = linprog(-K,A,B,[],[],0*K,n+0*K);      phi = round(x');
    end
    % random phi
    %phi = round(rand(1,m^n)*n);
    % adversarial phi
    %phi = zeros(1,m^n);
    %ii = find(K>0);
    %phi(ii) = n*ones(size(ii));
    
    ptil = pl(phi-ksig);
    %ptil = pl(phi-1);   %NO, def. don't do this -- too boku boku
    %ptil = (phi-ksig);
    
    if 0
      lhs = phi*K;
      %rhs = sum(pl(K)) + ptil*K;
      ii = find(phi==n);
      phi1 = phi; phi1(ii) = phi1(ii)-1;
      rhs = sum(pl(K)) + phi1*K;
      good = (lhs <= rhs+1e-9)
      if ~good
        'real stupid'
      keyboard
      end
      %works
    end
    
    lhs = ptil*K;
    rhs = Psi(K1,m,n-1);
    good = (lhs <= rhs+1e-9)
    if ~good
      'dont work'
      keyboard
    end
    
    if 0
      Kf1 = K1.*getK1(ptil,m,n);
      phi1 = Kf1 ./ K1; phi1 = phi1(:)';
      ii = find(~isfinite(phi1));
      phi1(ii) = zeros(size(ii));
      lhs = ptil*K;
      rhs = phi1*K1;
      good = (lhs <= rhs+1e-9)
      if ~good
        'nope'
        keyboard
      end
    end
    %checkphi1h;
    %checkptil
    %checkptildec
    
    %works(K,ptil,m,n)
    %works
  end
end
return

function b = checkptil
global m n A B K K1 phi
ksig = (K>0)';
ptil = (phi-ksig);
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

for ind1 = 1:mn
  x = ind2coord(ind1,MN);
  for ind2 = ind1+1:mn
    y = ind2coord(ind2,MN);
    if rho(x,y)==1
      b = abs(ptil(ind1)-ptil(ind2)) <= 1 - (sign(K(ind1))~=sign(K(ind2))) ...
          + 1e-10;
      if ~b
        'nope'
        keyboard
      end
    end
  end
end
return


function b = checkptildec
global m n A B K K1 phi
ksig = (K>0)';
ptil = (phi-ksig);
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

lhs = phi*K;
rhs = sum(K) + sumkphiy(K,ptil,m,n);

good = (lhs <= rhs+1e-9);
if ~good
  'nope -- checkptildec'
  keyboard
end
return

function b = checkphi1h
global m n A B K K1 phi
ksig = (K>0)';
ptil = (phi-ksig);
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

if 0
  % is phi 1st coord homogeneous?
  % NOT NECESSARILY
  %b = 1;
  bb = ones(n,1);
  for i=1:n
    b = 1;
    for y=1:m
      phiy = project(ptil,y,m,n,i);
      for z=y+1:m
        phiz = project(ptil,z,m,n,i);
        b = b & all(phiy==phiz);
        %if ~b
        %  keyboard
        %end
      end
    end
    bb(i) = b;
  end
  b = any(bb);
end

if 0
  % does any projection bound ptil*K?
  % NO
  bb = [];
  for i=1:n
    for y=1:m
      phiy = project(ptil,y,m,n,i);
      %(ptil*K - phiy*K1)
      bb(end+1) = (ptil*K <= phiy*K1 + 1e-10);
    end
  end
  b = any(bb);  
end

if 0
  % if nothing else, this is too unaesthetic to be true
  % nope, fails (try m=2,n=3, run for a bit)
  [A1,B1] = lipab(m,n1);
  bb=[];
  for i=1:n
  %for i=1
    PTIL = zeros(m,m^(n-1));
    phi1 = zeros(1,m^(n-1));
    for y=1:m
      PTIL(y,:) = project(ptil,y,m,n,i);
    end
    for x=1:length(K1)
      if K1(x)>0
        phi1(x) = max(PTIL(:,x));
      else
        phi1(x) = min(PTIL(:,x));
      end
    end
    phi1 = min(phi1,n1);
    %blip = all(A1*phi1' <= B1+1e-10);
    %if ~all(A1*phi1' <= B1+1e-10)
    %  'not lip'
    %  keyboard
    %end
    %bbnd = (ptil*K <= phi1*K1 + 1e-10);
    %b = (blip & bbnd);
    b1 = (ptil*K <= phi1*K1 + 1e-10);
    b2 = (phi1*K1 <= Psi(K1,m,n-1) + 1e-10);
    % even this is false
    b = b1 & b2;
    bb(end+1)=b;
  end
  b = any(bb);  %seems to hold
  %b = all(bb);   %doesn't hold
end

if 1
  % nope, doesn't guarantee lip
  % i've seen this before, duh
  
  phi1 = zeros(1,mn1);
  for x1nd = 1:mn1
    x = ind2coord(x1nd,MN1);
    f = zeros(m,1);
    for y = 1:m
      yx = [y x];
      yxind = coord2ind(yx,MN);
      f(y) = ptil(yxind);
    end
    if K1(x1nd)>0
      %phi1(x1nd) = max(f);
      phi1(x1nd) = ceil(mean(f));
    else
      %phi1(x1nd) = min(f);
      phi1(x1nd) = floor(mean(f));
    end
  end
  %phi1 = min(phi1,n1);
  % ok, we don't care if it's lipschitz
  % but it better respect the inequality
  b1 = (ptil*K <= phi1*K1 + 1e-10);
  % NO, b2 fails,
  % and fails again...
  b2 = (phi1*K1 <= Psi(K1,m,n-1) + 1e-10);
  b = b1 & b2;
  
  %[A1,B1] = lipab(m,n1);
  %if ~all(A1*phi1' <= B1+1e-10)
  %  'not lip'
  %  keyboard
  %end
  %b = (ptil*K <= phi1*K1 + 1e-10);
end

if 0
  for y=1:m
    K1y = project(K1,y,m,n-1,n-1);
    ptily = project(ptil,y,m,n-1,n-1);
    b = (ptily*K1y <= Psi(K1y,m,n-2) + 1e-10);
    if ~b,  'doesnt bound',  keyboard,end
  end
end
  
if ~b,  'bad bound',  keyboard,end
return

function Ky = project(K,y,m,n,i)
%global m n
MN = repmat([m],[1 n]);
Ky = [];
mn = m^n;
for ind = 1:mn
  z = ind2coord(ind,MN);
  %if z(end)==y
  %if z(1)==y
  if z(i)==y
    Ky(end+1) = K(ind);
  end
end
%Ky=Ky(:);
Ky = reshape(Ky,size(K(1:length(Ky))));
return





function b = works1
global m n A B K K1 phi
K1 = getK1(K,m,n);
n1 = n-1;
b = 1;
lhs = phi * K;
rhs = pl(sum(K)) + sumkphiy(K,phi,m,n);
tryfail(lhs,rhs,'simple fails');
% seems to be holding up...

lhs = rhs;
rhs = Psi(K,m,n);
tryfail(lhs,rhs,'no good at all');
% it's indeed too crude -- abandon approach!!
return

% now the trick is to massage phiy
% into a function in \Phi_{n-1}
% that's "big" enough to bound phi*K
% yet "small" enough to be bounded by \psin{n-1}(Ky)

% we get Lipschitz for free: projections of Lip functions
% are Lip. 
%simplest thing that comes to mind: 
%if max(phiy)=n then phiy = phiy - 1;
[A,B] = lipab(m,n1); 
lhs1 = phi*K;
rhs1 = pl(sum(K));
for y=1:m
  Ky = getky(K,y,m,n);
  phiy = getky(phi,y,m,n);
  lhs2 = phiy*Ky;
  rhs2 = Psi(Ky,m,n-1);
  tryfail(lhs2,rhs2,'next step, simple');
  
  % here is our massage:

  if 0
    [x,fval] = linprog(-Ky,A,B,[],[],0*Ky,n1+0*Ky);
    phiy = round(x');
    
    lhs2 = phiy*Ky;
    rhs2 = Psi(Ky,m,n-1);
    tryfail(lhs2,rhs2,'next step, simple');
    
    rhs1 = rhs1 + phiy*Ky;
  end
  
  if 0
    phiy = getky(phi,y,m,n);
    phiy = phiy - (max(phiy)==n); % OK, this one fails (first step)
    lhs2 = phiy*Ky;
    rhs2 = Psi(Ky,m,n-1);
    tryfail(lhs2,rhs2,'next step fails');
    
    phiy = getky(phi,y,m,n);
    ii = find(phiy==n); phiy(ii) = phiy(ii)-1;
    lhs21 = phiy*Ky;
    rhs21 = Psi(Ky,m,n-1);
    tryfail(lhs21,rhs21,'next step1 fails');
    
    %rhs1 = rhs1 + phiy*Ky;
    rhs1 = rhs1 + max(rhs2,rhs21);
  end
end
%tryfail(lhs1,rhs1,'first step fails');

return
ii = find(phi==n);
ptil = phi; ptil(ii) = ptil(ii)-1;
S=0;
lhs = ptil * K;
K1 = getK1(K,m,n);
rhs = Psi(K1,m,n-1);
good = (lhs <= rhs+1e-9)
if ~good
  'N0PE 1'
  keyboard
end
return

for y=1:m
  Ky = getky(K,y,m,n);
  %Ky1 = getK1(Ky,m,n-1);
  phiy = getky(phi,y,m,n);
  %phiy = pl(phiy-1);
  phiy = (phiy-1);

  lhs = phiy*Ky;
  S = S + phiy*Ky;
  %rhs = Psi(Ky1,m,n-2);
  rhs = Psi(Ky,m,n-1);
  good = (lhs <= rhs+1e-9)
  if ~good
    'dont work'
    keyboard
  end
end

lhs = phi*K;
rhs = sum(K) + S;
good = (lhs <= rhs+1e-9)
if ~good
  'dont work'
  keyboard
end

b = 1;
return


function b = works0(K,phi,m,n)
S=0;
for y=1:m
  Ky = getky(K,y,m,n);
  %Ky1 = getK1(Ky,m,n-1);
  phiy = getky(phi,y,m,n);
  %phiy = pl(phiy-1);
  phiy = (phiy-1);

  lhs = phiy*Ky;
  S = S + phiy*Ky;
  %rhs = Psi(Ky1,m,n-2);
  rhs = Psi(Ky,m,n-1);
  good = (lhs <= rhs+1e-9)
  if ~good
    'dont work'
    keyboard
  end
end

lhs = phi*K;
rhs = sum(K) + S;
good = (lhs <= rhs+1e-9)
if ~good
  'dont work'
  keyboard
end

b = 1;
return

function sketchpad8
global m n A B
m=2
n=3

while 1
  K = genK(m,n);
  ksig = (K>0)';
  %phi = randlip(m,n);
  [A,B] = lipab(m,n);
  [x,fval] = linprog(-K,A,B,[],[],0*K,n+0*K);
  phi = round(x');
  %phi = round(rand(1,m^n)*n);
  phi = zeros(1,m^n);
  ii = find(K>0);
  phi(ii) = n*ones(size(ii));

  
  %phi1 = getphi1s(K,phi);

  lhs = phi*K
  if 1
  S = 0;
  sy = 0;
  %ptil = pl(phi-1);
  ptil = pl(phi-ksig);
  for y=1:m
    Ky = getky(K,y,m,n);
    %phiy = getky(phi,y,m,n);
    phiy = getky(ptil,y,m,n);
    %S = S + phiy*Ky;
    lhs = phiy*Ky;
    rhs = Psi(Ky,m,n-1);
    good = (lhs <= rhs+1e-9)
    if ~good
      'bady'
      keyboard
    end
    
    %S = S + phiy*Ky;
    if 0
      Psiky = Psi(Ky,m,n-1);
      
      ii = find(phiy==n)
      ptil = zeros(size(phiy));
      ptil(ii) = ones(size(ii));
      ptil = phiy - ptil;
      
      lhs = phiy*Ky;
      %rhs = ptil*Ky + sum(Ky);
      rhs = ptil*Ky + sum(Ky(ii));
      sy = sy + sum(Ky(ii));
      good = (lhs <= rhs+1e-9)
      if ~good
        'bady1'
        keyboard
      end
      
      %lhs = Psiky + sum(Ky(ii));
      %rhs = ptil*Ky + sum(Ky);
      %rhs = ptil*Ky + sum(Ky(ii));
      %good = (lhs <= rhs+1e-9)
      %if ~good
      %  'bady2'
      %  keyboard
      %end
      
      
      %fy = min(phiy);
      %S = S + Psiky + fy*sum(Ky);  % false
      %ptil = phiy - fy;
      %S = S + ptil*Ky + fy*sum(Ky); % true
      
      %S = S + fy*sum(Ky);
      
      lhs = Psi(Ky,m,n-1) + sum(Ky(ii));
      %rhs = 
      good = (lhs <= rhs+1e-9)
      if ~good
        'bady1'
        keyboard
      end
    end
  end
  end
  
  %lhs = sumkphiy(K,phi,m,n);
  %lhs = S;
  %lhs = phi*K;
  %rhs = Psi(K,m,n);
  %rhs = sum(K);
  
  %rhs = sum(K) + phi1*K
  %rhs = sum(pl(K)) + phi1*K

  %lhs = sy;
  %rhs = sum(K);
  % false
  
  %lhs = sumky(K,m,n) + sy;
  %rhs = Psi(K,m,n);
  %rhs = sum(K) + S;
  rhs = sumkphiy(K,phi,m,n)+sum(pl(K));
  
  %good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end

end
return


function sketchpad7
% NOT TRUE FOR ALL SUBSETS
% not even for "good" sets
global m n
m=2
n=2
mn = m^n;
MN = repmat([m],[1 n]);

while 1
  K = genK(m,n);
  
  %inds = list_all_inds(MN);
  inds = list_all_ind_g(repmat({[0 1]},[1 mn]));
  sky = sumky(K,m,n);
  rhs = Psi(K,m,n);
  for ii=1:size(inds,1)
  %for ii=size(inds,1)
  %for ii=1
    i = find(inds(ii,:));
    b = goodset(i,m,n);
    if b
      lhs = sky + sum(K(i));
      good = (lhs <= rhs+1e-9)
      if ~good
        'bad1'
        keyboard
      end
    end
  end
  %lhs = sumky(K,m,n) + sum(pl(K));
  %lhs = sumky(K) + sum((K));
  %lhs = sumky(K,m,n);
  %rhs = Psi(K,m,n);
  % FALSE!!
  % and I know why!!
  %good = (lhs <= rhs+1e-9)
  %if ~good
  %  'bad1'
  %  keyboard
  %end

end
return






function sketchpad4
global m n A B
m=2
n=2
[A,B] = lipab(m,n);

while 1
  K = genK(m,n);
  phi = randlip(m,n);
  %phi = round(rand(1,m^n)*n);
  phi = zeros(1,m^n);
  ii = find(K>0);
  phi(ii) = n*ones(size(ii));

  
  %phi1 = getphi1s(K,phi);

  %lhs = phi*K
  S = 0;
  for y=1:m
    Ky = getky(K,y,m,n);
    phiy = getky(phi,y,m,n);
    %S = S + phiy*Ky;
    %lhs = phiy*Ky;
    %rhs = Psi(Ky,m,n-1);
    %good = (lhs <= rhs+1e-9)
    %if ~good
    %  'bady'
    %  keyboard
    %end
    % that's false
    
    Psiky = Psi(Ky,m,n-1);
    
    ii = find(phiy==n);
    ptil = zeros(size(phiy));
    ptil(ii) = ones(size(ii));
    ptil = phiy - ptil;
    
    lhs = phiy*Ky;
    %rhs = ptil*Ky + sum(Ky);
    rhs = ptil*Ky + sum(Ky(ii));
    good = (lhs <= rhs+1e-9)
    if ~good
      'bady'
      keyboard
    end
    
    %fy = min(phiy);
    %S = S + Psiky + fy*sum(Ky);  % false
    %ptil = phiy - fy;
    %S = S + ptil*Ky + fy*sum(Ky); % true
    
    %S = S + fy*sum(Ky);
  end

  
  %lhs = sumkphiy(K,phi,m,n);
  %lhs = S;
  lhs = phi*K;
  rhs = Psi(K,m,n);
  %rhs = sum(K);
  
  %rhs = sum(K) + phi1*K
  %rhs = sum(pl(K)) + phi1*K

  good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end

end
return


function sketchpad3
global m n
m=3
n=3

while 1
  K = genK(m,n);
  
  %lhs = sumky(K,m,n) + sum(pl(K));
  %lhs = sumky(K) + sum((K));
  lhs = sumky(K,m,n);
  rhs = Psi(K,m,n);
  % FALSE!!
  % and I know why!!
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end

end
return


function sketchpad2
global m n A B
m=2
n=3
[A,B] = lipab(m,n);

while 1
  K = genK(m,n);
  %phi = randlip(m,n);
  %phi = round(rand(1,m^n)*n);
  phi = zeros(1,m^n);
  ii = find(K>0);
  phi(ii) = n*ones(size(ii));

  
  phi1 = getphi1(K,phi);

  lhs = phi*K
  
  %rhs = sum(K) + phi1*K
  rhs = sum(pl(K)) + phi1*K

  good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end

end
return


function sketchpad9
global m n
m=2
n=2

while 1
  K = genK(m,n);
  
  lhs = sumky(K,m,n) + sum(pl(K));
  %lhs = sumky(K) + sum((K));
  rhs = Psi(K,m,n);
  % FALSE!!
  % and I know why!!
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end

end
return


function phi1 = getphi1(K,phi)
global m n A B
[A,B] = lipab(m,n);
%A = [A; -K'];
%B = [B; sum(K)-phi*K];
%f = ones(size(K));
%[x,fval] = linprog(f,A,B,K',phi*K-sum(K),0*K,0*K+n-1);
%[x,fval] = linprog(f,A,B,[],[],0*K,0*K+n-1);
[x,fval] = linprog(-K,A,B,[],[],0*K,0*K+n-1);
%[x,fval] = linprog(-K,A,B,[],[],0*K,0*K+n);
%phi1 = round(x');
phi1 = x';
%if ~( phi*K <= sum(K)+phi1*K + 1e-9)
%  keyboard
%end
return

function sketchpad0
global m n
m=2
n=2

while 1
  K = genK(m,n);
  %phi = randlip(m,n);
  %phi = round(rand(1,m^n)*n);
  %phi = (rand(1,m^n)*n);
  
  phi = zeros(1,m^n);
  ii = find(K>0);
  phi(ii) = n*ones(size(ii));
  
  %lhs = sumky(K) + sum(K);
  %rhs = Psi(K,m,n);
  % this is num. true
  % PROVEN!!
  
  %K1 = getK1(K,m,n);
  %lhs = sumky(K);
  %rhs = Psi(K1,m,n-1);
  % this is false
  
  lhs = phi*K
  ksig = (K>0)';
  phi1 = pl(phi-1);
  %phi1 = pl(phi-ksig);
  %phi1 = phi-1;
  pz = find(~phi);
  k1 = K;
  k1(pz) = zeros(size(pz));
  %rhs = sum(K) + phi1*K;
  rhs = sum(k1) + phi1*k1
  
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad1'
    keyboard
  end
  
  rhs = sum(k1) + sumkphiy(k1,phi1)
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad2'
    keyboard
  end

  rhs = sum(k1) + sumky(k1)
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad3'
    keyboard
  end

  rhs = Psi(K,m,n);
  good = (lhs <= rhs+1e-9)
  if ~good
    'bad4'
    keyboard
  end
  
end


return

function S = sumky(K,m,n)
%global m n
S = 0;
for y=1:m
  Ky = getky(K,y,m,n);
  S = S + Psi(Ky,m,n-1);
end
return

function S = sumkphiy(K,phi,m,n)
%global m n
S = 0;
for y=1:m
  Ky = getky(K,y,m,n);
  phiy = getky(phi,y,m,n);
  S = S + phiy*Ky;
end
return


function Ky = getky(K,y,m,n)
%global m n
MN = repmat([m],[1 n]);
Ky = [];
mn = m^n;
for ind = 1:mn
  z = ind2coord(ind,MN);
  if z(end)==y
  %if z(1)==y
    Ky(end+1) = K(ind);
  end
end
%Ky=Ky(:);
Ky = reshape(Ky,size(K(1:length(Ky))));
return


function b = goodset(S,m,n)
% S is "good" if it has the following property:
% if x=x_1 x_2 ... x_n is in S
% and x_i = c then
% for all j\neq i, for all y_j in \X
% y = y_1 ... y_i-1 c y_i+1 ... y_n is in S

% hmm... maybe just for x1?

mn = m^n;
MN = repmat([m],[1 n]);
Y = list_all_ind(repmat([m],[1 n-1]));
b = 1;
for xi=S
  x = ind2coord(xi,MN);
  %for i=1:n
  for i=1
    c = x(i);
    XY = [repmat(c,[size(Y,1) 1]) Y];
    xyi = coord2ind(XY,MN);
    b = b & all(ismember(xyi,S));
  end
end
  
return



function tryfail(lhs,rhs,failstr)
global m n A B K K1 phi ksig ptil bet
good = (lhs <= rhs+1e-9);
if ~good
  failstr
  %save SKETCHFAIL m n A B K K1 phi ksig ptil
  keyboard
end
return


function [A,B,LB,UB] = alfab(K,m,n)
n1 = n-1;
MN  = repmat([m],[1 n ]);
MN1 = repmat([m],[1 n1]);
mn  = m^n;
mn1 = m^n1;

A=zeros(0,mn);
B=zeros(0,1);
rind = 0;
for ind1 = 1:mn
  for ind2 = ind1+1:mn
    x = ind2coord(ind1,MN);
    y = ind2coord(ind2,MN);
    d = rho(x,y);
    if (sign(K(ind1))==sign(K(ind2)))
      % signs equal -- ordinary Lip. cond
      if 1 % condition (ii).a
        for s = [-1,1]
          rind = rind+1;
          A(rind,ind1) =  s;
          A(rind,ind2) = -s;
          B(rind,1) = d;
        end
      end
    elseif d==1
      if (K(ind1)>0)
        pos = ind1;
        neg = ind2;
      else
        pos = ind2;
        neg = ind1;
      end
      if 1  % condition (ii).b  -- DO need this!!
        rind = rind+1;
        A(rind,neg) = -1;
        A(rind,pos) =  1;
        B(rind,1) = 0;
        rind = rind+1;
        A(rind,neg) =  1;
        A(rind,pos) = -1;
        B(rind,1) = 2;
      end
    end
  end
end

LB = 0*K;
UB = LB + n - (~~pl(K));
%UB = LB + n + 1 - (~~pl(K));
%UB = LB + n + 1;
%UB = LB + n;
return